十大排序算法（C语言）

1以个人使用频率及掌握程度进行如下排列。2以下都是从小到大排序。3一般记住哪个用哪个。建议不要只会冒泡排序数据量大了一定会超时。4小技巧可以C的sort()函数会方便很多。5最后如果有错误请各位指出。1、快速排序1时间复杂度O(nlog2n)2快速排序 - 百度百科不稳定/*先调用划分函数再进行左右递归排序*/intpartition(inta[],inti,intj)//注意i、j都是下标。i为起始下标j为末尾下标。{intta[i];while(ij){while(a[j]tij)j--;//右边的数都比t大建议加上等号这样效率更高if(ij)a[i]a[j];while(a[i]tij)i;//左边的数都比t小建议加上等号这样效率更高if(ij)a[j--]a[i];}a[i]t;returni;//返回下标}voidQuickSort(inta[],inti,intj){intk;if(ij){kpartition(a,i,j);//使用划分函数把序列分成两部分QuickSort(a,i,k-1);//对前半部分递归排序QuickSort(a,k1,j);//对后半部分递归排序}}/*快速排序的填坑法*/intPartition(inta[],inti,intj){intstarti;//保留开头下标intta[i];while(ij){while(ija[j]t)j--;while(ija[i]t)i;//注意只能有一个等号且必须是a[i]t的情况if(ij)//swap(a,i,j);//交换{inttema[i];a[i]a[j];a[j]tem;}//swap(a,start,i);//把基数填入inttema[start];a[start]a[i];a[i]tem;returni;}2、选择排序1O(n2)2选择排序_百度百科不稳定voidSelectionSort(inta[],intn){inti,j;intminId;//每一轮中最小值的下标intt;for(i0;in-1;i){//一共n-1趟minIdi;for(ji1;jn;j){//每次找出从a[j]到a[n-1]中最小的值和a[i]进行交换if(a[j]a[minId]){minIdj;//记录当前一趟最小值的下标}}/*交换*/ta[i];a[i]a[minId];a[minId]t;}}3、冒泡排序1O(n2)2冒泡排序_百度百科稳定voidBubbleSort(inta[],intn){inti,j;intt;for(i0;in-1;i){//外层循环n-1趟for(j0;jn-1-i;j){//第一次比较n-1次 每趟比较到jn-1-iif(a[j]a[j1]){//相邻进行比较逆序则进行交换ta[j];a[j]a[j1];a[j1]t;}}}/*上面的for循环还可以写成这样只不过改变了一下i的初始值*//*for(i1;in;i){//外层循环n-1趟 for(j0;jn-i;j){//第一次比较n-1次 每趟比较到jn-i if(a[j]a[j1]){//相邻进行比较逆序则进行交换 ta[j]; a[j]a[j1]; a[j1]t; } } }*/}4、插入排序1:O(n2)2插入排序_百度百科稳定voidInsertionSort(inta[],intn){inti,j;intt;for(i1;in;i){ta[i];//t每次都等于当前要插入的数字for(ji-1;j0ta[j];jj-1){a[j1]a[j];//往后挪因为t小}a[j1]t;//将t插入到当前正确的位置因为t刚好大于a[j],所以要插入到a[j1]}}5、希尔排序1O(n1.3~2)2希尔排序_百度百科3下面这两个函数唯一区别就是是否把外层循环放在主函数。4把 ShellSort_2( ) 函数中的 g 换成 1 就是上面的插入排序。不稳定voidShellSort_1(inta[],intn){inti,j;intt;intg;//表示间隔gapfor(gn/2;g0;gg/2){//初始g为数组长度的一半for(ig;in;i){ta[i];for(ji-g;j0ta[j];jj-g){a[jg]a[j];}a[jg]t;}}}#includestdio.hvoidShellSort_2(inta[],intn,intg){inti,j;intt;/*把下面的g换成1就是上面的插入排序*/for(ig;in;i){ta[i];for(ji-g;j0ta[j];jj-g){a[jg]a[j];}a[jg]t;}}intmain(){inta[4]{1,4,5,7};intg;//初始g等于数组长度的一半for(g4/2;g0;gg/2){//初始gn/2ShellSort_2()函数需要多次调用上面的ShellSort_1()调用一次即可。ShellSort_2(a,4,g);}//输出for(i0;in;i){printf(%d、 ,a[i]);}return0;}6、归并排序1:O(nlog2n)2归并排序_百度百科稳定/*针对数组a[]进行两段区间a[s1]-a[e1]和a[s2]-a[e2]的合并 a[]是要排序的数组s1是起始下标e1末尾下标s2起始下标e2末尾下标b[]辅助数组*/voidMerge(inta[],ints1,inte1,ints2,inte2,intb[]){intks1;intis1;//保留s1,便于后面数组复制while(s1e1s2e2){if(a[s1]a[s2]){b[k]a[s1];}else{b[k]a[s2];}}while(s1e1)b[k]a[s1];while(s2e2)b[k]a[s2];k--;while(ki){//把排好的数据复制到数组aa[k]b[k];k--;}}voidMergeSort(inta[],inti,intj,intb[]){//a[]要排序的数组i起始下标j末尾下标b[]辅助数组intk;if(ij){k(ij)/2;MergeSort(a,i,k,b);MergeSort(a,k1,j,b);Merge(a,i,k,k1,j,b);//合并}}7、堆排序1O(nlog2n)2堆排序_百度百科不稳定#defineLeftChild(i)(2*(i)1)voidBuildDown(inta[],intn,introotId){introot;intchildId;root[rootId];childIdLeftChild(rootId);while(childIdn){if(childId!n-1a[childId1]a[childId])childId;if(roota[childId]){a[rootId]a[childId];rootIdchildId;childIdLeftChild(rootId);}else{break;}}a[rootId]root;}voidHeapSort(inta[],intn){introotId;intt;inti;for(introotId(n-2)/2;rootId0;rootId--){BuildDown(a,n,rootId);}for(in-1;i0;i--){ta[0];a[0]a[i];a[i]t;}BuildDown(a,i,0);}8、基数排序1:O(k(mn))2基数排序_百度百科稳定9、桶排序1:O(nk)2桶排序_百度百科10、计数排序1O(n)2计数排序_百度百科稳定