数据结构：10大经典排序

排序

1、冒泡排序

// 冒泡排序
#include <stdlib.h>#include <stdio.h>

// 采用两层循环实现的方法。
// 参数arr是待排序数组的首地址，len是数组元素的个数。
void bubblesort1(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int ii;    // 排序的趟数的计数器。
  int jj;    // 每趟排序的元素位置计数器。
  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。

  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48  
  for(ii=len-1;ii>0;ii--)  // 一共进行len-1趟比较。
  {for(jj=0;jj<ii;jj++)  // 每趟只需要比较0......ii之间的元素，ii之后的元素是已经排序好的。
    {if(arr[jj]>arr[jj+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。
      {itmp=arr[jj+1];
        arr[jj+1]=arr[jj];
        arr[jj]=itmp;}}}}

// 采用递归实现的方法。
// 参数arr是待排序数组的首地址，len是数组元素的个数。
void bubblesort2(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int ii;    // 排序的元素位置计数器。
  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。

  for(ii=0;ii<len-1;ii++)  // 每趟只需要比较0......len-1之间的元素，len-1之后的元素是已经排序好的。
  {if(arr[ii]>arr[ii+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。
    {itmp=arr[ii+1];
      arr[ii+1]=arr[ii];
      arr[ii]=itmp;}}

  bubblesort2(arr,--len);}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  int len=sizeof(arr)/sizeof(int);

  bubblesort1(arr,len);

  // 显示排序结果。
  int ii;for(ii=0;ii<len;ii++) printf("%2d ",arr[ii]);

  printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

2、选择排序

// 选择排序
#include <stdlib.h>#include <stdio.h>

// 交换两个变量的值。
void swap(int *x,int *y){
  int itmp=*x;
  *x=*y;
  *y=itmp;}

// 采用两层循环实现的方法。
// 参数arr是待排序数组的首地址，len是数组元素的个数。
void selectsort1(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int ii;      // 排序的趟数的计数器。
  int jj;      // 每趟排序的元素位置计数器。
  int iminpos; // 每趟循环选出的最小值的位置（数组的下标）。

  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48  
  for(ii=0;ii<len-1;ii++)  // 一共进行len-1趟比较。
  {iminpos=ii;for(jj=ii+1;jj<len;jj++)  // 每趟只需要比较ii+1......len-1之间的元素，ii之前的元素是已经排序好的。
    {
      // 找出值更小的元素，记下它的位置。
      if(arr[jj]<arr[iminpos])iminpos=jj;}

    // 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
    if(iminpos!=ii) swap(&arr[ii],&arr[iminpos]);}}

// 采用递归实现的方法。
// 参数arr是待排序数组的首地址，len是数组元素的个数。
void selectsort2(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int ii;        // 排序的趟数的计数器。
  int iminpos=0; // 每趟循环选出的最小值的位置（数组的下标）。

  for(ii=1;ii<len;ii++){
    // 找出值更小的元素，记下它的位置。
    if(arr[ii]<arr[iminpos])iminpos=ii;}

  // 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
  if(iminpos!=0) swap(&arr[0],&arr[iminpos]);

  selectsort2(arr+1,--len);}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  //int arr[]={3,4,5,1};
  int len=sizeof(arr)/sizeof(int);

  // selectsort1(arr,len);  // 采用两层循环排序的方法。
  selectsort2(arr,len);  // 采用递归排序的方法。

  // 显示排序结果。
  int ii;for(ii=0;ii<len;ii++) printf("%2d ",arr[ii]);

  printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

3、插入排序

// 插入排序
#include <stdlib.h>#include <stdio.h>

// 参数arr是待排序数组的首地址，len是数组元素的个数。
void insertsort(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int itmp;  // 当前需要排序的元素的值。
  int ii;    // 需要排序元素的计数器。
  int jj;    // 插入排序时，需要后移元素的计数器。

  for(ii=1;ii<len;ii++){itmp=arr[ii];    // 待排序元素

    // 从已排序的最右边开始，把大于当前排序的元素后移。
    // for(jj=ii-1;(jj>=0&&arr[jj]>itmp);jj--)for(jj=ii-1;jj>=0;jj--){if(arr[jj]<=itmp)break;

      arr[jj+1]=arr[jj]; // 逐个元素后移。
    }

    arr[jj+1]=itmp; // 插入当前排序元素。
  }}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  int len=sizeof(arr)/sizeof(int);

  insertsort(arr,len);   // 调用插入排序函数对数组排序。

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

4、希尔排序

// 希尔排序
#include <stdlib.h>#include <stdio.h>

// 对希尔排序中的单个组进行排序。
// arr-待排序的数组，len-数组总的长度，ipos-分组的起始位置，istep-分组的步长（增量）。
void groupsort(int *arr, int len, int ipos,int istep){
  int itmp;  // 当前需要排序的元素的值。
  int ii;    // 需要排序元素的计数器。
  int jj;    // 插入排序时，需要后移元素的计数器。

  for(ii=ipos+istep;ii<len;ii=ii+istep){itmp=arr[ii];    // 待排序元素
      
    // 从已排序的最右边开始，把大于当前排序的元素后移。
    // for(jj=ii-istep;(jj>=0&&arr[jj]>itmp);jj=jj-istep)for(jj=ii-istep;jj>=0;jj=jj-istep){if(arr[jj]<=itmp)break;  

      arr[jj+istep]=arr[jj];  // 逐个元素后移。
    }

    arr[jj+istep]=itmp; // 插入当前排序元素。
  }}

// 希尔排序，arr是待排序数组的首地址，len是数组的大小。
void shellsort(int *arr,unsigned int len){
  int ii,istep;

  // istep为步长，每次减为原来的一半取整数，最后一次必定为1。
  for(istep=len/2;istep>0;istep=istep/2){
    // 共istep个组，对每一组都执行插入排序。
    for(ii=0;ii<istep;ii++){
      groupsort(arr,len,ii,istep);}}}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  int len=sizeof(arr)/sizeof(int);

  shellsort(arr,len);   // 调用插入排序函数对数组排序。

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

5、快速排序

// 快速排序
#include <stdlib.h>#include <stdio.h>

void quicksort(int *arr,unsigned int len){if(len<2)return;  // 数组的元素小于2个就不用排序了。

  int itmp=arr[0];  // 选取最左边的数作为中心轴。
  int ileft=0;      // 左下标。
  int iright=len-1; // 右下标。
  int imoving=2;    // 当前应该移动的下标，1-左下标；2-右下标。

  while(ileft<iright){if(imoving==2) // 移动右下标的情况。
    {
      // 如果右下标位置元素的值大于等于中心轴，继续移动右下标。
      if(arr[iright]>=itmp){ iright--;continue;}
      
      // 如果右下标位置元素的值小于中心轴，把它填到左下标的坑中。
      arr[ileft]=arr[iright];
      ileft++;    // 左下标向右移动。
      imoving=1;  // 下次循环将移动左下标。
      continue;}if(imoving==1) // 移动左下标的情况。
    {
      // 如果左下标位置元素的值小等于中心轴，继续移动左下标。
      if(arr[ileft]<=itmp){ ileft++;continue;}

      // 如果左下标位置元素的值大于中心轴，把它填到右下标的坑中。
      arr[iright]=arr[ileft];
      iright--;   // 右下标向左移动。
      imoving=2;  // 下次循环将移动右下标。
      continue;}}

  // 如果循环结束，左右下标重合，把中心轴的值填进去。
  arr[ileft]=itmp;

  quicksort(arr,ileft);             // 对中心轴左边的序列进行排序。
  quicksort(arr+ileft+1,len-ileft-1); // 对中心轴右边的序列进行排序。
}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  int len=sizeof(arr)/sizeof(int);

  quicksort(arr,len);   // 调用插入排序函数对数组排序。

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

6、归并排序

// 采用递归的方法实现归并排序
#include <stdlib.h>#include <stdio.h>#include <string.h>

// 采用递归的方法实现归并排序函数。
// arr-待排序数组的首地址，arrtmp-用于排序的临时数组的首地址
// start-排序区间第一个元素的位置，end-排序区间最后一个元素的位置。
void _mergesort(int *arr,int *arrtmp,int start,int end){
  // 如果start>=end，表示该区间的元素少于两个，递归终止。
  if(start>=end)return; 

  int mid=start+(end-start)/2;  // 计算排序区间中间的位置。

  int istart1=start,iend1=mid;  // 区间左边元素的第一和最后一个元素的位置。
  int istart2=mid+1,iend2=end;  // 区间右边元素的第一和最后一个元素的位置。

  _mergesort(arr,arrtmp,istart1,iend1);   // 对区间左边元素递归排序。
  _mergesort(arr,arrtmp,istart2,iend2);   // 对区间右边元素递归排序。

  int ii=start; // 已排序数组arrtmp的计数器。

  // 把区间左右两边数列合并到已排序数组arrtmp中。
  while(istart1<=iend1 && istart2<=iend2)
    arrtmp[ii++]=arr[istart1]<arr[istart2] ? arr[istart1++]: arr[istart2++];

  // 把左边数列其它的元素追加到已排序数组。
  while(istart1<=iend1) arrtmp[ii++]=arr[istart1++];

  // 把右边数列其它的元素追加到已排序数组。
  while(istart2<=iend2) arrtmp[ii++]=arr[istart2++];

  // 把已排序数组arrtmp中的元素复制到arr中。
  memcpy(arr+start,arrtmp+start,(end-start+1)*sizeof(int));}

// 排序主函数，arr为待排序的数组的地址，len为数组的长度。
void mergesort(int *arr,unsigned int len){if(len<2)return;  // 小于两个元素不需要排序。

  int arrtmp[len];  // 分配一个与待排序数组相同大小的数组。

  _mergesort(arr,arrtmp,0,len-1);  // 调用递归函数进行排序。
}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};
  int len=sizeof(arr)/sizeof(int);

  mergesort(arr,len);

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

// 采用循环的方法实现归并排序函数
#include <stdlib.h>#include <stdio.h>#include <string.h>

int min(int x,int y){return x<y ? x : y;}  // 取x和y中的较小者的值。

// 采用循环实现归并排序，arr-待排序数组的首地址，len--待排序数组的长度。
void mergesort(int *arr,unsigned int len){if(len<2)return;  // 小于两个元素不需要排序。

  int *aa=arr;     // aa指向待排序的数组。
  int *bb=(int *)malloc(len*sizeof(int)); // bb指向已排序的数组。

  int iseg;    // 区间分段的计数器，1,2,4,8,16,...
  int istart;  // 区间起始位置的计数器。

  // 排序的趟数的循环。
  for(iseg=1;iseg<len;iseg=iseg*2){
    // 每趟排序选取区间的循环。
    for(istart=0;istart<len;istart=istart+iseg*2){
      // 把每个区间分成两部分，ilow是起始位置，imid是中间位置，imax是结束位置。
      int ilow=istart;
      int imid=min(istart+iseg,len);     // 考虑分段不均的情况，imid不能超出len。
      int imax=min(istart+iseg*2,len);   // 考虑分段不均的情况，imax也不能超出len。

      int ii=ilow; // 已排序数组的计数器。
      int istart1=ilow,iend1=imid;  // 待排序左边数列的起始和结束位置。
      int istart2=imid,iend2=imax;  // 待排序右边数列的起始和结束位置。

      // 把待排序左右两边数列合并到已排序数组。
      while((istart1<iend1)&&(istart2<iend2))
        bb[ii++]=aa[istart1]<aa[istart2] ? aa[istart1++]: aa[istart2++];

      // 把左边数列其它的元素追加到已排序数组。
      while(istart1<iend1) bb[ii++]=aa[istart1++];

      // 把右边数列其它的元素追加到已排序数组。
      while(istart2<iend2) bb[ii++]=aa[istart2++];}

    // 交换一下两个数组的指针，准备下一趟的排序。
    int *ptmp=aa;aa=bb;bb=ptmp;}

  // 如果aa指向的不是原始数组的指针，把aa中的内容复制到arr中。
  if(aa != arr){
    memcpy(arr,aa,len*sizeof(int));

    bb = aa;}

  free(bb);}

int main(int argc,char *argv[]){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48,10};
  int len=sizeof(arr)/sizeof(int);

  mergesort(arr,len);

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

7、堆排序

// 堆排序
#include <stdio.h>#include <stdlib.h>

// 交换两个元素的值。
void swap(int *a,int *b){ int temp=*b; *b=*a; *a=temp;}

// 采用循环实现heapify（元素下沉）。
// arr-待排序数组的地址，start-待heapify节点的下标，end-待排序数组最后一个元素的下标。
void heapify(int *arr,int start,int end){
  // 确定父节点和左子节点的数组下标。
  int dad=start;
  int son=dad*2+1;

  // 如果子节点的下标没有超出范围，循环继续。
  while(son<=end){ 
    // 先比较两個子节点大小，选择最大的。
    if((son+1<=end)&&(arr[son]<arr[son+1])) son++;

    // 如果父节点大于子节点代表调整完毕，直接跳出函数。
    if(arr[dad]>arr[son])return;

    // 否则交换父子內容再继续子节点和孙节点比较。
    swap(&arr[dad],&arr[son]);dad=son;son=dad*2+1;}}

// 采用递归实现heapify。
void heapify1(int *arr,int start,int end){
  // 确定父节点和左子节点的数组下标。
  int dad=start;
  int son=dad*2+1;

  // 如果子节点的下标没有超出范围，循环继续。
  if(son>end )return;

  // 先比较两個子节点大小，选择最大的。
  if((son+1<=end)&&(arr[son]<arr[son+1])) son++;

  // 如果父节点大于子节点代表调整完毕，直接跳出函数。
  if(arr[dad]>arr[son])return;

  // 否则交换父子內容再继续子节点和孙节点比较。
  swap(&arr[dad],&arr[son]);

  heapify(arr,son,end);}

void heapsort(int *arr, int len){
  int ii;

  // 初始化堆，从最后一個父节点开始调整。
  for(ii=(len-1)/2;ii>=0;ii--) heapify(arr,ii,len-1);

  // 把第一个元素和堆最后一个元素交换，然后重新调整，直到排序完毕。
  for(ii=len-1;ii>0;ii--){
    swap(&arr[0],&arr[ii]);
    heapify(arr,0,ii-1);}}

int main(){
  int arr[]={44,3,38,5,47,15,36,26,27,2,46,4,19,50,48};

  int len=sizeof(arr)/sizeof(int);

  heapsort(arr,len);

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

8、计数排序

// 计数排序（基础版）
#include <stdio.h>#include <stdlib.h>#include <string.h>

// 获取待排序数组的最大元素的值。
int arrmax(int *arr,unsigned int len){
  int ii=0;
  int imax=0;for(ii=0;ii<len;ii++)if(imax<arr[ii])imax=arr[ii];return imax;}

// 计数排序主函数，arr-待排序数组的地址，len-数组的长度。
void countsort(int *arr,unsigned int len){if(len<2)return;

  int imax=arrmax(arr,len);  // 获取待排序数组的最大元素的值。
  int arrtmp[imax+1];        // 临时数组的大小为imax+1。

  memset(arrtmp,0,sizeof(arrtmp));  // 初始化临时数组。

  int ii,jj,kk;
  
  // 临时数组计数。
  for(ii=0;ii<len;ii++) arrtmp[arr[ii]]++;

  // 把临时数组计数的内容填充到arr中。
  ii=0;for(jj=0;jj<imax+1;jj++){for(kk=0;kk<arrtmp[jj];kk++) arr[ii++]=jj;}}

int main(){
  int arr[]={2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2};

  int len=sizeof(arr)/sizeof(int);

  int xx;for(xx=0;xx<len;xx++) printf("%2d ",arr[xx]); printf("\n");

  countsort(arr,len);

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

9、桶排序

// 桶排序
#include <stdlib.h>#include <stdio.h>#include <string.h>

// 采用两层循环实现冒泡排序的方法。
// 参数arr是待排序数组的首地址，len是数组元素的个数。
void bubblesort(int *arr,unsigned int len){if(len<2)return; // 数组小于2个元素不需要排序。

  int ii;    // 排序的趟数的计数器。
  int jj;    // 每趟排序的元素位置计数器。
  int itmp;  // 比较两个元素大小时交换位置用到的临时变量。

  // 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48  
  for(ii=len-1;ii>0;ii--)  // 一共进行len-1趟比较。
  {for(jj=0;jj<ii;jj++)  // 每趟只需要比较0......ii之间的元素，ii之后的元素是已经排序好的。
    {if(arr[jj]>arr[jj+1])  // 如果前面的元素大于后面的元素，则交换它位的位置。
      {itmp=arr[jj+1];
        arr[jj+1]=arr[jj];
        arr[jj]=itmp;}}}}

// 桶排序主函数，参数arr是待排序数组的首地址，len是数组元素的个数。
void bucketsort(int *arr,unsigned int len){
  int buckets[5][5];   // 分配五个桶。
  int bucketssize[5];  // 每个桶中元素个数的计数器。

  // 初始化桶和桶计数器。
  memset(buckets,0,sizeof(buckets));
  memset(bucketssize,0,sizeof(bucketssize));

  // 把数组arr的数据放入桶中。
  int ii=0;for(ii=0;ii<len;ii++){
    buckets[arr[ii]/10][bucketssize[arr[ii]/10]++]=arr[ii];}

  // 对每个桶进行冒泡排序。
  for(ii=0;ii<5;ii++){
    bubblesort(buckets[ii],bucketssize[ii]);}

  // 把每个桶中的数据填充到数组arr中。
  int jj=0,kk=0;for(ii=0;ii<5;ii++){for(jj=0;jj<bucketssize[ii];jj++)
      arr[kk++]=buckets[ii][jj];}}

int main(int argc,char *argv[]){
  int arr[]={21,3,30,44,15,36,6,10,9,19,25,48,5,23,47};
  int len=sizeof(arr)/sizeof(int);

  int xx;for(xx=0;xx<len;xx++) printf("%2d ",arr[xx]); printf("\n");

  bucketsort(arr,len);

  // 显示排序结果。
  int ii;for(ii=0;ii<len;ii++) printf("%2d ",arr[ii]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}

10、基数排序

#include <stdlib.h>#include <stdio.h>#include <string.h>

// 获取数组arr中最大值，arr-待排序的数组，len-数组arr的长度。
int arrmax(int *arr,unsigned int len){
  int ii,imax;imax=arr[0];for(ii=1;ii<len;ii++)if(arr[ii]>imax)imax=arr[ii];return imax;}

// 对数组arr按指数位进行排序。
// arr-待排序的数组，len-数组arr的长度。
// exp-排序指数，exp=1：按个位排序；exp=10：按十位排序；......
void _radixsort(int *arr,unsigned int len,unsigned int exp){
  int ii;
  int result[len];       // 存放从桶中收集后数据的临时数组。
  int buckets[10]={0};   // 初始化10个桶。

  // 遍历arr，将数据出现的次数存储在buckets中。
  for(ii=0;ii<len;ii++)
    buckets[(arr[ii]/exp)%10]++;

  // 调整buckets各元素的值，调整后的值就是arr中元素在result中的位置。
  for(ii=1;ii<10;ii++)
    buckets[ii]=buckets[ii]+buckets[ii-1];

  // 将arr中的元素填充到result中。
  for(ii=len-1;ii>=0;ii--){
    int iexp=(arr[ii]/exp)%10;
    result[buckets[iexp]-1]=arr[ii];
    buckets[iexp]--;}
  
  // 将排序好的数组result复制到数组arr中。
  memcpy(arr,result,len*sizeof(int));}

// 基数排序主函数，arr-待排序的数组，len-数组arr的长度。
void radixsort(int *arr,unsigned int len){
  int imax=arrmax(arr,len);    // 获取数组arr中的最大值。

  int iexp;    // 排序指数，iexp=1：按个位排序；iexp=10：按十位排序；......

  // 从个位开始，对数组arr按指数位进行排序。
  for(iexp=1;imax/iexp>0;iexp=iexp*10){
    _radixsort(arr,len,iexp);
    int yy; printf("exp=%-5d  ",iexp);for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");}}

int main(int argc,char *argv[]){
  int arr[]={144,203,738,905,347,215,836,26,527,602,946,504,219,750,848};
  int len=sizeof(arr)/sizeof(int);

  radixsort(arr,len);  // 基数排序。

  // 显示排序结果。
  int yy;for(yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");

  // system("pause");  // widnows下的C启用本行代码。

  return0;}