C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)經(jīng)典10大排序算法刨析
更新時(shí)間：2022年02月25日 16:47:22 作者：橙子@C
這篇文章主要介紹了C語(yǔ)言中常用的10種排序算法及代碼實(shí)現(xiàn),開(kāi)發(fā)中排序的應(yīng)用需要熟練的掌握，因?yàn)槭腔A(chǔ)內(nèi)容，那C語(yǔ)言有哪些排序算法呢？本文小編就來(lái)詳細(xì)說(shuō)說(shuō),需要的朋友可以參考一下
1、冒泡排序
// 冒泡排序
#include <stdlib.h>
#include <stdio.h>
// 采用兩層循環(huán)實(shí)現(xiàn)的方法。
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void bubblesort1(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int ii; // 排序的趟數(shù)的計(jì)數(shù)器。
int jj; // 每趟排序的元素位置計(jì)數(shù)器。
int itmp; // 比較兩個(gè)元素大小時(shí)交換位置用到的臨時(shí)變量。
// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48
for (ii=len-1;ii>0;ii--) // 一共進(jìn)行l(wèi)en-1趟比較。
{
for (jj=0;jj<ii;jj++) // 每趟只需要比較0......ii之間的元素，ii之后的元素是已經(jīng)排序好的。
{
if (arr[jj]>arr[jj+1]) // 如果前面的元素大于后面的元素，則交換它位的位置。
{
itmp=arr[jj+1];
arr[jj+1]=arr[jj];
arr[jj]=itmp;
}
}
}
}
// 采用遞歸實(shí)現(xiàn)的方法。
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void bubblesort2(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int ii; // 排序的元素位置計(jì)數(shù)器。
int itmp; // 比較兩個(gè)元素大小時(shí)交換位置用到的臨時(shí)變量。
for (ii=0;ii<len-1;ii++) // 每趟只需要比較0......len-1之間的元素，len-1之后的元素是已經(jīng)排序好的。
{
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);
// 顯示排序結(jié)果。
int ii;
for (ii=0;ii<len;ii++) printf("%2d ",arr[ii]);
printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
2、選擇排序
// 選擇排序
#include <stdlib.h>
#include <stdio.h>
// 交換兩個(gè)變量的值。
void swap(int *x,int *y)
{
int itmp=*x;
*x=*y;
*y=itmp;
}
// 采用兩層循環(huán)實(shí)現(xiàn)的方法。
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void selectsort1(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int ii; // 排序的趟數(shù)的計(jì)數(shù)器。
int jj; // 每趟排序的元素位置計(jì)數(shù)器。
int iminpos; // 每趟循環(huán)選出的最小值的位置（數(shù)組的下標(biāo)）。
// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48
for (ii=0;ii<len-1;ii++) // 一共進(jìn)行l(wèi)en-1趟比較。
{
iminpos=ii;
for (jj=ii+1;jj<len;jj++) // 每趟只需要比較ii+1......len-1之間的元素，ii之前的元素是已經(jīng)排序好的。
{
// 找出值更小的元素，記下它的位置。
if (arr[jj]<arr[iminpos]) iminpos=jj;
}
// 如果本趟循環(huán)的最小的元素不是起始位置的元素，則交換它們的位置。
if (iminpos!=ii) swap(&arr[ii],&arr[iminpos]);
}
}
// 采用遞歸實(shí)現(xiàn)的方法。
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void selectsort2(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int ii; // 排序的趟數(shù)的計(jì)數(shù)器。
int iminpos=0; // 每趟循環(huán)選出的最小值的位置（數(shù)組的下標(biāo)）。
for (ii=1;ii<len;ii++)
{
// 找出值更小的元素，記下它的位置。
if (arr[ii]<arr[iminpos]) iminpos=ii;
}
// 如果本趟循環(huán)的最小的元素不是起始位置的元素，則交換它們的位置。
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); // 采用兩層循環(huán)排序的方法。
selectsort2(arr,len); // 采用遞歸排序的方法。
// 顯示排序結(jié)果。
int ii; for (ii=0;ii<len;ii++) printf("%2d ",arr[ii]);
printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
3、插入排序
// 插入排序
#include <stdlib.h>
#include <stdio.h>
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void insertsort(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int itmp; // 當(dāng)前需要排序的元素的值。
int ii; // 需要排序元素的計(jì)數(shù)器。
int jj; // 插入排序時(shí)，需要后移元素的計(jì)數(shù)器。
for (ii=1;ii<len;ii++)
{
itmp=arr[ii]; // 待排序元素
// 從已排序的最右邊開(kāi)始，把大于當(dāng)前排序的元素后移。
// 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]; // 逐個(gè)元素后移。
}
arr[jj+1]=itmp; // 插入當(dāng)前排序元素。
}
}
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); // 調(diào)用插入排序函數(shù)對(duì)數(shù)組排序。
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
4、希爾排序
// 希爾排序
#include <stdlib.h>
#include <stdio.h>
// 對(duì)希爾排序中的單個(gè)組進(jìn)行排序。
// arr-待排序的數(shù)組，len-數(shù)組總的長(zhǎng)度，ipos-分組的起始位置，istep-分組的步長(zhǎng)（增量）。
void groupsort(int *arr, int len, int ipos,int istep)
{
int itmp; // 當(dāng)前需要排序的元素的值。
int ii; // 需要排序元素的計(jì)數(shù)器。
int jj; // 插入排序時(shí)，需要后移元素的計(jì)數(shù)器。
for (ii=ipos+istep;ii<len;ii=ii+istep)
{
itmp=arr[ii]; // 待排序元素
// 從已排序的最右邊開(kāi)始，把大于當(dāng)前排序的元素后移。
// 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]; // 逐個(gè)元素后移。
}
arr[jj+istep]=itmp; // 插入當(dāng)前排序元素。
}
}
// 希爾排序，arr是待排序數(shù)組的首地址，len是數(shù)組的大小。
void shellsort(int *arr,unsigned int len)
{
int ii,istep;
// istep為步長(zhǎng)，每次減為原來(lái)的一半取整數(shù)，最后一次必定為1。
for (istep=len/2;istep>0;istep=istep/2)
{
// 共istep個(gè)組，對(duì)每一組都執(zhí)行插入排序。
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); // 調(diào)用插入排序函數(shù)對(duì)數(shù)組排序。
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
5、快速排序
// 快速排序
#include <stdlib.h>
#include <stdio.h>
void quicksort(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組的元素小于2個(gè)就不用排序了。
int itmp=arr[0]; // 選取最左邊的數(shù)作為中心軸。
int ileft=0; // 左下標(biāo)。
int iright=len-1; // 右下標(biāo)。
int imoving=2; // 當(dāng)前應(yīng)該移動(dòng)的下標(biāo)，1-左下標(biāo)；2-右下標(biāo)。
while (ileft<iright)
{
if (imoving==2) // 移動(dòng)右下標(biāo)的情況。
{
// 如果右下標(biāo)位置元素的值大于等于中心軸，繼續(xù)移動(dòng)右下標(biāo)。
if (arr[iright]>=itmp) { iright--; continue; }
// 如果右下標(biāo)位置元素的值小于中心軸，把它填到左下標(biāo)的坑中。
arr[ileft]=arr[iright];
ileft++; // 左下標(biāo)向右移動(dòng)。
imoving=1; // 下次循環(huán)將移動(dòng)左下標(biāo)。
continue;
}
if (imoving==1) // 移動(dòng)左下標(biāo)的情況。
{
// 如果左下標(biāo)位置元素的值小等于中心軸，繼續(xù)移動(dòng)左下標(biāo)。
if (arr[ileft]<=itmp) { ileft++; continue; }
// 如果左下標(biāo)位置元素的值大于中心軸，把它填到右下標(biāo)的坑中。
arr[iright]=arr[ileft];
iright--; // 右下標(biāo)向左移動(dòng)。
imoving=2; // 下次循環(huán)將移動(dòng)右下標(biāo)。
continue;
}
}
// 如果循環(huán)結(jié)束，左右下標(biāo)重合，把中心軸的值填進(jìn)去。
arr[ileft]=itmp;
quicksort(arr,ileft); // 對(duì)中心軸左邊的序列進(jìn)行排序。
quicksort(arr+ileft+1,len-ileft-1); // 對(duì)中心軸右邊的序列進(jìn)行排序。
}
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); // 調(diào)用插入排序函數(shù)對(duì)數(shù)組排序。
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
6、歸并排序
// 采用遞歸的方法實(shí)現(xiàn)歸并排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// 采用遞歸的方法實(shí)現(xiàn)歸并排序函數(shù)。
// arr-待排序數(shù)組的首地址，arrtmp-用于排序的臨時(shí)數(shù)組的首地址
// start-排序區(qū)間第一個(gè)元素的位置，end-排序區(qū)間最后一個(gè)元素的位置。
void _mergesort(int *arr,int *arrtmp,int start,int end)
{
// 如果start>=end，表示該區(qū)間的元素少于兩個(gè)，遞歸終止。
if (start>=end) return;
int mid=start+(end-start)/2; // 計(jì)算排序區(qū)間中間的位置。
int istart1=start,iend1=mid; // 區(qū)間左邊元素的第一和最后一個(gè)元素的位置。
int istart2=mid+1,iend2=end; // 區(qū)間右邊元素的第一和最后一個(gè)元素的位置。
_mergesort(arr,arrtmp,istart1,iend1); // 對(duì)區(qū)間左邊元素遞歸排序。
_mergesort(arr,arrtmp,istart2,iend2); // 對(duì)區(qū)間右邊元素遞歸排序。
int ii=start; // 已排序數(shù)組arrtmp的計(jì)數(shù)器。
// 把區(qū)間左右兩邊數(shù)列合并到已排序數(shù)組arrtmp中。
while (istart1<=iend1 && istart2<=iend2)
arrtmp[ii++]=arr[istart1]<arr[istart2] ? arr[istart1++] : arr[istart2++];
// 把左邊數(shù)列其它的元素追加到已排序數(shù)組。
while (istart1<=iend1) arrtmp[ii++]=arr[istart1++];
// 把右邊數(shù)列其它的元素追加到已排序數(shù)組。
while (istart2<=iend2) arrtmp[ii++]=arr[istart2++];
// 把已排序數(shù)組arrtmp中的元素復(fù)制到arr中。
memcpy(arr+start,arrtmp+start,(end-start+1)*sizeof(int));
}
// 排序主函數(shù)，arr為待排序的數(shù)組的地址，len為數(shù)組的長(zhǎng)度。
void mergesort(int *arr,unsigned int len)
{
if (len<2) return; // 小于兩個(gè)元素不需要排序。
int arrtmp[len]; // 分配一個(gè)與待排序數(shù)組相同大小的數(shù)組。
_mergesort(arr,arrtmp,0,len-1); // 調(diào)用遞歸函數(shù)進(jìn)行排序。
}
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);
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
// 采用循環(huán)的方法實(shí)現(xiàn)歸并排序函數(shù)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int min(int x,int y) { return x<y ? x : y; } // 取x和y中的較小者的值。
// 采用循環(huán)實(shí)現(xiàn)歸并排序，arr-待排序數(shù)組的首地址，len--待排序數(shù)組的長(zhǎng)度。
void mergesort(int *arr,unsigned int len)
{
if (len<2) return; // 小于兩個(gè)元素不需要排序。
int *aa=arr; // aa指向待排序的數(shù)組。
int *bb=(int *)malloc(len*sizeof(int)); // bb指向已排序的數(shù)組。
int iseg; // 區(qū)間分段的計(jì)數(shù)器，1,2,4,8,16,...
int istart; // 區(qū)間起始位置的計(jì)數(shù)器。
// 排序的趟數(shù)的循環(huán)。
for (iseg=1;iseg<len;iseg=iseg*2)
{
// 每趟排序選取區(qū)間的循環(huán)。
for (istart=0;istart<len;istart=istart+iseg*2)
{
// 把每個(gè)區(qū)間分成兩部分，ilow是起始位置，imid是中間位置，imax是結(jié)束位置。
int ilow=istart;
int imid=min(istart+iseg,len); // 考慮分段不均的情況，imid不能超出len。
int imax=min(istart+iseg*2,len); // 考慮分段不均的情況，imax也不能超出len。
int ii=ilow; // 已排序數(shù)組的計(jì)數(shù)器。
int istart1=ilow,iend1=imid; // 待排序左邊數(shù)列的起始和結(jié)束位置。
int istart2=imid,iend2=imax; // 待排序右邊數(shù)列的起始和結(jié)束位置。
// 把待排序左右兩邊數(shù)列合并到已排序數(shù)組。
while ((istart1<iend1) && (istart2<iend2))
bb[ii++]=aa[istart1]<aa[istart2] ? aa[istart1++] : aa[istart2++];
// 把左邊數(shù)列其它的元素追加到已排序數(shù)組。
while (istart1<iend1) bb[ii++]=aa[istart1++];
// 把右邊數(shù)列其它的元素追加到已排序數(shù)組。
while (istart2<iend2) bb[ii++]=aa[istart2++];
}
// 交換一下兩個(gè)數(shù)組的指針，準(zhǔn)備下一趟的排序。
int *ptmp=aa; aa=bb; bb=ptmp;
}
// 如果aa指向的不是原始數(shù)組的指針，把a(bǔ)a中的內(nèi)容復(fù)制到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);
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
7、堆排序
// 堆排序
#include <stdio.h>
#include <stdlib.h>
// 交換兩個(gè)元素的值。
void swap(int *a,int *b) { int temp=*b; *b=*a; *a=temp; }
// 采用循環(huán)實(shí)現(xiàn)heapify（元素下沉）。
// arr-待排序數(shù)組的地址，start-待heapify節(jié)點(diǎn)的下標(biāo)，end-待排序數(shù)組最后一個(gè)元素的下標(biāo)。
void heapify(int *arr,int start,int end)
{
// 確定父節(jié)點(diǎn)和左子節(jié)點(diǎn)的數(shù)組下標(biāo)。
int dad=start;
int son=dad*2+1;
// 如果子節(jié)點(diǎn)的下標(biāo)沒(méi)有超出范圍，循環(huán)繼續(xù)。
while (son<=end)
{
// 先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的。
if ((son+1<=end) && (arr[son]<arr[son+1])) son++;
// 如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)。
if (arr[dad]>arr[son]) return;
// 否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較。
swap(&arr[dad],&arr[son]);
dad=son;
son=dad*2+1;
}
}
// 采用遞歸實(shí)現(xiàn)heapify。
void heapify1(int *arr,int start,int end)
{
// 確定父節(jié)點(diǎn)和左子節(jié)點(diǎn)的數(shù)組下標(biāo)。
int dad=start;
int son=dad*2+1;
// 如果子節(jié)點(diǎn)的下標(biāo)沒(méi)有超出范圍，循環(huán)繼續(xù)。
if (son>end ) return;
// 先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的。
if ((son+1<=end) && (arr[son]<arr[son+1])) son++;
// 如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)。
if (arr[dad]>arr[son]) return;
// 否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較。
swap(&arr[dad],&arr[son]);
heapify(arr,son,end);
}
void heapsort(int *arr, int len)
{
int ii;
// 初始化堆，從最后一個(gè)父節(jié)點(diǎn)開(kāi)始調(diào)整。
for (ii=(len-1)/2;ii>=0;ii--) heapify(arr,ii,len-1);
// 把第一個(gè)元素和堆最后一個(gè)元素交換，然后重新調(diào)整，直到排序完畢。
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);
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
8、計(jì)數(shù)排序
// 計(jì)數(shù)排序（基礎(chǔ)版）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 獲取待排序數(shù)組的最大元素的值。
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;
}
// 計(jì)數(shù)排序主函數(shù)，arr-待排序數(shù)組的地址，len-數(shù)組的長(zhǎng)度。
void countsort(int *arr,unsigned int len)
{
if (len<2) return;
int imax=arrmax(arr,len); // 獲取待排序數(shù)組的最大元素的值。
int arrtmp[imax+1]; // 臨時(shí)數(shù)組的大小為imax+1。
memset(arrtmp,0,sizeof(arrtmp)); // 初始化臨時(shí)數(shù)組。
int ii,jj,kk;
// 臨時(shí)數(shù)組計(jì)數(shù)。
for (ii=0;ii<len;ii++) arrtmp[arr[ii]]++;
// 把臨時(shí)數(shù)組計(jì)數(shù)的內(nèi)容填充到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);
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
9、桶排序
// 桶排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// 采用兩層循環(huán)實(shí)現(xiàn)冒泡排序的方法。
// 參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void bubblesort(int *arr,unsigned int len)
{
if (len<2) return; // 數(shù)組小于2個(gè)元素不需要排序。
int ii; // 排序的趟數(shù)的計(jì)數(shù)器。
int jj; // 每趟排序的元素位置計(jì)數(shù)器。
int itmp; // 比較兩個(gè)元素大小時(shí)交換位置用到的臨時(shí)變量。
// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48
for (ii=len-1;ii>0;ii--) // 一共進(jìn)行l(wèi)en-1趟比較。
{
for (jj=0;jj<ii;jj++) // 每趟只需要比較0......ii之間的元素，ii之后的元素是已經(jīng)排序好的。
{
if (arr[jj]>arr[jj+1]) // 如果前面的元素大于后面的元素，則交換它位的位置。
{
itmp=arr[jj+1];
arr[jj+1]=arr[jj];
arr[jj]=itmp;
}
}
}
}
// 桶排序主函數(shù)，參數(shù)arr是待排序數(shù)組的首地址，len是數(shù)組元素的個(gè)數(shù)。
void bucketsort(int *arr,unsigned int len)
{
int buckets[5][5]; // 分配五個(gè)桶。
int bucketssize[5]; // 每個(gè)桶中元素個(gè)數(shù)的計(jì)數(shù)器。
// 初始化桶和桶計(jì)數(shù)器。
memset(buckets,0,sizeof(buckets));
memset(bucketssize,0,sizeof(bucketssize));
// 把數(shù)組arr的數(shù)據(jù)放入桶中。
int ii=0;
for (ii=0;ii<len;ii++)
{
buckets[arr[ii]/10][bucketssize[arr[ii]/10]++]=arr[ii];
}
// 對(duì)每個(gè)桶進(jìn)行冒泡排序。
for (ii=0;ii<5;ii++)
{
bubblesort(buckets[ii],bucketssize[ii]);
}
// 把每個(gè)桶中的數(shù)據(jù)填充到數(shù)組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);
// 顯示排序結(jié)果。
int ii; for (ii=0;ii<len;ii++) printf("%2d ",arr[ii]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
10、基數(shù)排序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// 獲取數(shù)組arr中最大值，arr-待排序的數(shù)組，len-數(shù)組arr的長(zhǎng)度。
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;
}
// 對(duì)數(shù)組arr按指數(shù)位進(jìn)行排序。
// arr-待排序的數(shù)組，len-數(shù)組arr的長(zhǎng)度。
// exp-排序指數(shù)，exp=1：按個(gè)位排序；exp=10：按十位排序；......
void _radixsort(int *arr,unsigned int len,unsigned int exp)
{
int ii;
int result[len]; // 存放從桶中收集后數(shù)據(jù)的臨時(shí)數(shù)組。
int buckets[10]={0}; // 初始化10個(gè)桶。
// 遍歷arr，將數(shù)據(jù)出現(xiàn)的次數(shù)存儲(chǔ)在buckets中。
for (ii=0;ii<len;ii++)
buckets[(arr[ii]/exp)%10]++;
// 調(diào)整buckets各元素的值，調(diào)整后的值就是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]--;
}
// 將排序好的數(shù)組result復(fù)制到數(shù)組arr中。
memcpy(arr,result,len*sizeof(int));
}
// 基數(shù)排序主函數(shù)，arr-待排序的數(shù)組，len-數(shù)組arr的長(zhǎng)度。
void radixsort(int *arr,unsigned int len)
{
int imax=arrmax(arr,len); // 獲取數(shù)組arr中的最大值。
int iexp; // 排序指數(shù)，iexp=1：按個(gè)位排序；iexp=10：按十位排序；......
// 從個(gè)位開(kāi)始，對(duì)數(shù)組arr按指數(shù)位進(jìn)行排序。
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); // 基數(shù)排序。
// 顯示排序結(jié)果。
int yy; for (yy=0;yy<len;yy++) printf("%2d ",arr[yy]); printf("\n");
// system("pause"); // widnows下的C啟用本行代碼。
return 0;
}
到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)經(jīng)典10大排序算法刨析的文章就介紹到這了,更多相關(guān)C語(yǔ)言 排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了 C++11 智能指針之shared_ptr的相關(guān)知識(shí)，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言鍵盤(pán)控制走迷宮小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-06-06
C++標(biāo)準(zhǔn)庫(kù)封裝的vector數(shù)組
這篇文章主要介紹了C++標(biāo)準(zhǔn)庫(kù)封裝的vector數(shù)組，vector創(chuàng)建的對(duì)象包含眾多封裝好的函數(shù)，想了解其相關(guān)資料的小伙伴可以參考下面文章內(nèi)容，希望對(duì)你的學(xué)習(xí)有所幫助2022-03-03
C語(yǔ)言實(shí)現(xiàn)一個(gè)閃爍的圣誕樹(shù)
本文詳細(xì)講解了C語(yǔ)言實(shí)現(xiàn)一個(gè)閃爍的圣誕樹(shù)，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)圖形裁減，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C語(yǔ)言實(shí)現(xiàn)餐飲管理與點(diǎn)餐系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)餐飲管理與點(diǎn)餐系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-01-01
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
#if 0還有一個(gè)重要的用途就是用來(lái)當(dāng)成注釋?zhuān)绻阆胍⑨尩某绦蚝荛L(zhǎng)，這個(gè)時(shí)候#if 0是最好的，保證不會(huì)犯錯(cuò)誤2013-09-09
C語(yǔ)言讀取寫(xiě)入ini配置文件的方法實(shí)現(xiàn)
本文主要介紹了C語(yǔ)言讀取寫(xiě)入ini配置文件的方法實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
都說(shuō)STL是數(shù)據(jù)容器與算法的高度組合,在前面的文章中我們介紹了常見(jiàn)的幾種容器,vector、list、map、deque等,今天我們?cè)賮?lái)介紹下STL中常用的一些算法,需要的朋友可以參考下2024-02-02