十大排序算法

这是楼主找实习的时候准备的面试十大排序算法，其中参考了很多其他人的帖子，也有自己敲的，注释都写在demo里面了，希望能够帮到大家。因为楼主是非科班出身，所以程序难免有些错误，仅供大家参考理解哈0.0~；同时这里分享十大排序算法的图解，配合动图来理解还是可以的！！

十大排序算法复杂度(图是盗的0.0)

教你们一句话记住不稳定排序有哪些：
快（快速）些（希尔）选（选择）一堆（堆排序）美女一起玩是不稳的，其他都是稳定的~ （ps:这句话是师兄教我的0.0）；
涉及到需要二分操作的复杂度都是nlogn，平均复杂度和稳定性问得比较多哦！
十大排序算法按照是否进行元素比较可以分为比较类和非比较类两种。

打印测试demo

void print(int *array,int size){
        int i;
    for(i=0;i<size;++i){
        printf("%d",array[i]);
        if(i!=size-1)
            printf(",");    
    }
    printf("\n");
}

冒泡排序(比较类)

从头到尾两两进行对比排序直到序列数为1，复杂度为n^2；适用数据量不大，基本有序情况

void maopao_sort(int *array,int size){
    int i,j,temp;
    for(i=0;i<size-1;++i){//这里默认排到最后一个是不用比的，也只剩下一个，没得比了,所以减掉1 
        for(j=0;j<size-i-1;++j){//减掉i是因为每次最后的第i个元素已经有序不需要继续排序 
            if(array[j]>array[j+1]){
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
            }                
        }
    }
    print(array,10);        
}

选择排序(比较类)

选出最值，再从剩下的序列中继续选择最值，一直重复直到结束，使用两个for循环，复杂度为n^2，数据量不大，稳定性没有要求

void xuanze_sort(int *array,int size){
    int i,j,temp;
    for(i=0;i<size-1;++i){//还是最后一个不用比较，所以少一次 
        for(j=i+1;j<size;++j){//从第二个开始比较 
            if(array[i]>array[j]){
                temp=array[i];
                array[i]=array[j];
                array[j]=temp;
            }
        }        
    }
    print(array,10);
}

插入排序(比较类)

从第二个元素开始，依次与前面的元素对比并插入，循环直到最后一个，for+while，复杂度为n^2；局部/整体数据有序，数据量不大情况

void charu_sort(int *array,int size){
    int i,j,temp;
    for(i=1;i<size;++i){
        temp=array[i];//保存待比较的元素 
        j=i-1;//取出比较元素前一个，即已排好序的最后一个 
        while((j>=0)&&(array[j]>temp)){
            array[j+1]=array[j];//循环将比待比较大的元素移到后面 
            j--;            
        }
        array[j+1]=temp;//第j个为小于待比较的元素，所以待比较元素插在j+1个元素位置 
    }
    print(array,10);    
}

快速排序(比较类)

选择序列基准点，这里选择的是数组首元素，将小于的放在基准元素左边，大于的在右边，通过两个指针进行比较移动直到指针重叠，对基准点的左右两个子序列继续选择次基准点比较直到子序列数为1，使用while+while循环，复杂度为n*logn

void kuaisu_sort(int *array,int low,int hight){//参数为元素数组下标 
    if(low>=hight)  return; //递归的退出条件 
    int i=low;
    int j=hight;
    int temp=array[i];//取基准值 
    while(i<j){//当两个指针不重合的时候 
        while((i<j)&&(array[j]>=temp))//因为基准值取的是第一个，所以必须先在右边寻找大于基准值的元素，才可以把原先的位置填写为小于基准值的元素 
            j--;//j即为右边小于基准值的元素下标 
        array[i]=array[j];//将该元素放在基准值位置 
        while((i<j)&&(array[i]<=temp))//由上面可知右边j个元素出现空位，所以要从左边找大于基准值的元素 
            i++;
        array[j]=array[i];//同理，将第i个元素放入前面j元素的空位中 
    }
    array[i]=temp;//在这里说明i==j，即两个指针重合了，所以空位要补上基准值元素 
    kuaisu_sort(array,low,i-1);//递归从基准值左边 
    kuaisu_sort(array,i+1,hight);//递归从基准值右边 
}

堆排序(比较类)

先将序列排成小根堆/大根堆，然后交换头元素和尾元素，此时尾元素不参与，再从根开始继续变换成小根堆/大根堆，继续交换直到剩下两个元素，使用调整一次while+创建大根堆for+交换头尾for，复杂度为n*logn

void dui_adjustheap(int *array,int start,int end){//给定父节点调整该节点及以后节点满足父节点最大的要求，这个函数为调整作用 
    int dad=start;
    int son=2*dad+1;//左子节点，右为2*dad+2 
    while(son<end){ //当子节点为最后元素即再无子节点是可退出 
        if((son+1<end)&&(array[son]<array[son+1]))//若左节点小于右节点 
            son++;//较大节点下标 
        if(array[dad]>array[son]) break;//父节点最大，满足可退出 
        int temp;//父节点小于最大子节点，进行交换 
        temp=array[son];
        array[son]=array[dad];
        array[dad]=temp;
        dad=son;//选左节点为新父节点 
        son=2*dad+1; 
    }
}
void dui_sort(int *array,int size){
    int i=0,temp;
    //要先创建大根堆
    for(i=size/2-1;i>=0;--i)//这里除以2为求出二叉树中父节点的个数 ，这里要取到0，size/2为父节点个数，从0开始所以要减一 
        dui_adjustheap(array,i,size);//对每一个父节点进行调整
    for(i=size-1;i>=0;--i){//最后一个元素不需要比较，所以少一次，从0开始 
        temp=array[i];//从根头开始交换根尾元素 
        array[i]=array[0];
        array[0]=temp;
        dui_adjustheap(array,0,i);//每次交换后都要进行堆调整，使得重新变成大根堆 
    }
}

归并排序(比较类)

先分成包含两个及以下元素的子序列，各自排序后对子序列进行合并排序(分别对比两个子序列的首元素，小则存放，移到下一个元素继续比较)

void guibing_merge(int *array,int start,int mid,int end){
//输入的数组为左右两个有序的数组组成的，mid表示分界处，分成start-mid和mid+1-end两个子区间，注意这里传入的子区间都是已经排好序的 
    int *temp=(int *)malloc((end-start+1)*sizeof(int));//设置临时数组存放两个有序数组合并后的数组 
    int i=start;//第一个有序数组起始下标 
    int j=mid+1;//第一个有序数组末尾下标，即第二个有序数组起始下标 
    int k=0;//待比较元素下标 
    while((i<=mid)&&(j<=end)){//两个有序数组头元素分别进行比较，小的放入temp中，指针移到下一个继续比较 
        if(array[i]<array[j])
            temp[k++]=array[i++];//注意这里是先引用再++，即temp[k]=array[i]后再k+1,i+1 
        else
            temp[k++]=array[j++];        
    }
    while(i<=mid)//表示第二个数组先结束，这里将第一个数组剩下的都放到temp后面 
        temp[k++]=array[i++];
    while(j<=end)
        temp[k++]=array[j++];
    for(i=0;i<k;++i)//将排好序的temp中的元素放到原始数组中 
        array[start+i]=temp[i];//注意这里数组的偏移量设置 
    free(temp);
}
void guibing_sort(int *array,int start,int end) {
    if(start>=end)    return;
    int mid=(end+start)/2;//将待排序的数组分成两个 
    guibing_sort(array,start,mid);//递归处理前半部分数组 
    guibing_sort(array,mid+1,end);//递归处理后半部分数组 
    guibing_merge(array,start,mid,end);
   //当递归到只有两个元素的时候，也即传入的每个子区间只有一个元素，那么就可以对排好序的两个数组（各只有一个元素）进行合并 
}

希尔排序(比较类)

按间隔取出子序列，分别排序后再缩小间隔继续取子序列排序，直到间隔为1；适合比较较远距离的数据，进行一次比较可消除多个元素交换

void xier_sort(int *array,int size){
    int temp;
    int i,j;
    int incre=size/2;//增量按照一半取值 
    while(incre>=1){ 
        for(i=incre;i<size;++i){//从每一组的最后一个元素开始往前使用插入排序 
            temp=array[i];//待比较的元素 
            for(j=i-incre;(j>=0)&&(array[j]>temp);j=j-incre)//对每一组使用插入排序算法 
                array[j+incre]=array[j];
            array[j+incre]=temp;//这里可以和插入排序进行类比 
        }
        incre/=2;
    } 
    print(array,size);
}

基数排序(非比较类)

在0-9九个桶中(10*n的二维数组)，把序列中个位数a与桶相同的放在[a][x]中，再将二维数组从[0][x]~[9][x]排好，接着比较新序列的十位数(如果有)，直到比较到最高位

int base_getdigit(int m,int i){//取第i位的数字返回，i从1开始算个位 
    while(i>1){
        m/=10;
        i--;
    }
    return m%10;
}
void base_sort(int *array,int size){
    int temp[10][size];//使用二维数组来分类 
    int i,j,k,l,digit;
    memset(temp,-1,sizeof(temp));//初始化为-1才能保存数组中的0值 
    for(i=1;i<=10;++i){//按最多10个位数算 
        int flag=0;
        for(j=0;j<size;++j){//取出每个数的同一个数放入对应的二维数组中 
            digit=base_getdigit(array[j],i); 
            k=0;
            while(temp[digit][k]>=0) k++;//若对于二维数组有数据则下标要移到下一个 
            temp[digit][k]=array[j]; //放入空的数组中 
            if(digit) flag=1;//若有一个数不为0则置1 
        }
        if(!flag) break;//如果每个位置的数都是0，那么说明已经到了最大的位数，可以直接退出 
        l=0;
        for(j=0;j<10;++j){//将结果放回原数组中 
            k=0;
            while(temp[j][k]>=0)
                array[l++]=temp[j][k++];//要按照先进先出的顺序放 
        }
        memset(temp,-1,sizeof(temp));//重新初始化temp 
    }
    print(array,10);
}

计数排序(非比较类)

求序列最大值和最小值，创建包含最大值元素数组，按照序列元素对于数组下标+1统计个数后直接输出数组下标值，数组元素有几个就输出几个

void jishu_sort(int *array,int size){
    int i,max;
    max=array[0];
    for(i=1;i<size;++i)//求数组元素最大值 
        max=max>array[i]?max:array[i];            
    int temp[max+1];//temp要为最大值加1 
    memset(temp,0,sizeof(temp));//初始化为0 
    for(i=0;i<size;++i)
        temp[array[i]]+=1;//将对应的元素放入temp对应的下标中 
    int j=0;
    i=0;
    while(i<(max+1))//按照对应数组下标个数重新将元素放入原数组中 
        if(temp[i]!=0)
            while(temp[i])
                array[j++]=i++;
        else
            i+=1;        
    print(array,10);
}

桶排序(非比较类，宏观上)

求出序列最大值和最小值，将每个区间都分成一个桶，再把区间里的元素进行排序后将桶内的元素按区间排即可（这个桶排序是楼主自己写的demo，和计数排序不同，这里将待排序的数组元素放入以最大值和最小值为上下界的大区间中，再分成若干个子区间，每个子区取相同的间隔，并在子区间排好序后，按照区间顺序重新放回原数组中）

void tong_sort(int *array,int size){
    int i,max,min;
    int n,grp;
    max=array[0];
    min=array[0];
    for(i=1;i<size;++i){//求数组元素最大值和最小值 
        max=max>array[i]?max:array[i];
        min=min<array[i]?min:array[i];    
    }
    if(max<100) n=4;//最大值小于100取5个桶，大于1000则取10个桶 
    else if((max<1000)&&(max>100)) n=8;
    grp=(max-min)/n;//区间增量 
    n+=1;//防止数据溢出区间而再多设立一个桶 
    int temp[n][size+1];//分配桶 
    int j,k=1;
    for(i=0;i<n;++i){//初始化桶
       for(j=0;j<size+1;++j)
         temp[i][j]=-1;
    }
    for(i=0;i<n;++i)
        temp[i][0]=0;//temp[i][0]每个桶的首元素用来保存桶的元素个数 
    for(i=0;i<size;++i){//取待排序数组的每一个元素 
        j=0;
        while(j<n){//第几个桶 
            if((array[i]>=(min+grp*j))&&(array[i]<(min+grp*(j+1)))){//数组元素落在哪个区间 
                while(temp[j][k]>=0) k++;//若桶还有元素则往后移动下标 
                temp[j][0]+=1;//首元素，即元素个数计数加1                
                temp[j++][k]=array[i];//放入桶中 
                k=0;
                break;            
            }else j++;//不满足条件则看下一个桶                        
        }                
    }
    for(i=0;i<n;++i){//对每个桶内的元素进行排序，这里选用的是冒泡排序 
        if(temp[i][0]==0) continue;//桶内没有元素则退出 
        for(j=0;j<temp[i][0]-1;++j){//最后一个元素不用比较，所以减1 
            for(k=1;k<(temp[i][0]-j);++k){//桶内的元素从temp[i][1]开始取 
                if(temp[i][k]>temp[i][k+1]){
                    grp=temp[i][k];//grp做中间变量，进行元素间的交换 
                    temp[i][k]=temp[i][k+1];
                    temp[i][k+1]=grp;
                }                
            }
        }    
    }
    j=1;
    i=0;
    k=0;
    while((i<size)&&(k<n)){//将排好序的桶内的元素依次放入原数组中 
        if(temp[k][0]>0)
            for(j=1;j<temp[k][0]+1;++j)//第一个元素为每个桶的元素个数，这里大小要加1 
                array[i++]=temp[k][j]; 
        k+=1;                
    }
    print(array,10);
}