C语言数据结构经典10大排序算法刨析

// 采用两层循环实现的方法。

// 参数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

{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

{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

printf("\n");

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

// 交换两个变量的值。

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

{iminpos=ii;

for (jj=ii+1;jj

{// 找出值更小的元素，记下它的位置。

if (arr[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

if (arr[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

printf("\n");

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

// 参数arr是待排序数组的首地址，len是数组元素的个数。

void insertsort(int *arr,unsigned int len){if (len<2) return; // 数组小于2个元素不需要排序。

int itmp; // 当前需要排序的元素的值。

int ii; // 需要排序元素的计数器。

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

for (ii=1;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

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

// 对希尔排序中的单个组进行排序。

// 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

// 从已排序的最右边开始，把大于当前排序的元素后移。

// 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

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

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

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

{// 如果右下标位置元素的值大于等于中心轴，继续移动右下标。

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

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

// 采用递归的方法实现归并排序函数。

// 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]

// 把左边数列其它的元素追加到已排序数组。

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

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

int min(int x,int y) { return x

// 采用循环实现归并排序，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

for (istart=0;istart

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

// 把左边数列其它的元素追加到已排序数组。

while (istart1

// 把右边数列其它的元素追加到已排序数组。

while (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

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

// 交换两个元素的值。

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]

// 如果父节点大于子节点代表调整完毕，直接跳出函数。

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]

// 如果父节点大于子节点代表调整完毕，直接跳出函数。

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

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

#include #include #include

// 获取待排序数组的最大元素的值。

int arrmax(int *arr,unsigned int len){int ii=0;int imax=0;

for (ii=0;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

// 把临时数组计数的内容填充到arr中。

ii=0;for (jj=0;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

countsort(arr,len);

// 显示排序结果。

int yy; for (yy=0;yy

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

// 采用两层循环实现冒泡排序的方法。

// 参数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

{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

// 对每个桶进行冒泡排序。

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

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

bucketsort(arr,len);

// 显示排序结果。

int ii; for (ii=0;ii

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

// 获取数组arr中最大值，arr-待排序的数组，len-数组arr的长度。

int arrmax(int *arr,unsigned int len){int ii,imax;

imax=arr[0];

for (ii=1;iiimax) 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

// 调整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

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

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