c语言各种排序法详解

1、c语言各样排序法详解c语言各样排序法详解21/21c语言各样排序法详解适用文档一插入排序1.1直接插入排序基本思想：每次将一个待排序额记录按其重点码的大小插入到一个已经排好序的有序序列中，直到所有记录排好序。图解：代码实现：cppviewplaincopy/直接次序排序2.voidInsertSort(intr,intn)4.for(inti=2;in;i+)适用文档5.6.r0=ri;/设置哨兵7.for(intj=i-1;r0rj;j-)/找寻插入地点8.rj+1=rj;/记录后移9.rj+1=r0;10.11.for(intk=1;kn;k+)12.coutrk;13.coutn;14.

2、1.2希尔排序基本思想是：先将整个待排序记录序列切割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。图解：代码实现：cppviewplaincopy/希尔排序2.voidShellSort(intr,intn)适用文档4.inti;5.intd;6.intj;7.for(d=n/2;d=1;d=d/2)/以增量为d进行直接插入排序8.9.for(i=d+1;i0&r0rj;j=j-d)13.rj+d=rj;/记录后移d个地点14.rj+d=r0;15.16.for(i=1;in;i+)18.coutri;coutn;互换排序2.1起泡排序

3、起泡排序是互换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的重点码，假如反序则互换，直到没有反序的记录为止。图解：适用文档代码实现：cppviewplaincopy/起泡排序2.voidBubbleSort(intr,intn)4.inttemp;5.intexchange;6.intbound;7.exchange=n-1;/第一趟起泡排序的范围是r0到rn-18.while(exchange)/仅当上一趟排序有记录互换才进行本趟排序9.10.bound=exchange;11.exchange=0;12.for(intj=0;jrj+1)14.适用文档15.temp=rj;16.

4、rj=rj+1;17.rj+1=temp;18.exchange=j;/记录每一次发生记录互换的地点19.20.21.for(inti=0;in;i+)22.coutri;23.coutn;24.2.2迅速排序基本思想:经过一趟排序将要排序的数据切割成独立的两部分，此中一部分的所有数据都比其他一部分的所有数据都要小，此后再按此方法对这两部分数据分别进行迅速排序，整个排序过程能够递归进行，以此达到整个数据变为有序序列。图解：适用文档代码实现：cppviewplaincopy/迅速排序一次区分2.intPartition(intr,intfirst,intend)4.inti=first;/初始化

5、适用文档5.intj=end;6.inttemp;7.8.while(ij)9.10.while(ij&ri=rj)11.j-;/右侧扫描12.if(ij)13.14.temp=ri;/将较小记录互换到前面15.ri=rj;16.rj=temp;17.i+;18.19.while(ij&ri=rj)20.i+;/左侧扫描21.if(ij)22.23.temp=rj;24.rj=ri;25.ri=temp;/将较大记录互换到后边26.j-;27.28.29.returni;/i为轴值记录的最后地点30.31./迅速排序33.voidQuickSort(intr,intfirst,intend)3

6、4.35.if(firstend)36./递归纳束37.intpivot=Partition(r,first,end);/一次区分38.QuickSort(r,first,pivot-1);/递归地对左边子序列进行快速排序39.QuickSort(r,pivot+1,end);/递归地对右边子序列进行迅速排序40.适用文档41.42.三选择排序3.1简单项选择择排序基本思想：设所排序序列的记录个数为n。i取1,2,（Ri,Ri+1,Rn）中找出排序码最小的记录，与第,n-1,从所有n-i+1i个记录互换。履行个记录n-1趟后就达成了记录序列的排序。图解：适用文档代码实现：cppviewplai

7、ncopy/简单项选择择排序2.voidSelectSort(intr,intn)4.inti;5.intj;6.intindex;7.inttemp;8.for(i=0;in-1;i+)/对n个记录进行n-1趟简单项选择择排序9.10.index=i;11.for(j=i+1;jn;j+)/在无序区中采纳最小记录12.if(rjrindex)13.index=j;14.if(index!=i)15.16.temp=ri;17.ri=rindex;18.rindex=temp;19.20.21.for(i=0;in;i+)22.coutri;23.coutn;24.3.2堆排序堆的定义堆是拥有

8、以下性质的完满二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或许每个结点的值都大于或等于其左右孩子结点的值（大根堆）。大根堆和小根堆：根结点（亦称为堆顶）的重点字是堆里所有结点重点字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的重点字是堆里所有结点重点字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆其实是二叉堆Binary适用文档Heap），近似地可定义k叉堆。假定目前要优选结点的编号为k，堆中最后一个结点的编号为m，而且结点k的左右子树均是堆（即rk+1rm知足堆的条件），则优选算法用伪代码可描绘为：适用文档详细的优选代码以下：cppvi

9、ewplaincopy/优选法调整堆2.voidSift(intr,intk,intm)5.inti;6.intj;7.inttemp;8.i=k;9.j=2*i+1;/置i为要筛的结点，j为i的左孩子10.while(j=m)/优选还没有进行到叶子12.if(jm&rjrj)break;/根结点已经大于左右孩子中的较大者15.else16.17.temp=ri;18.ri=rj;19.rj=temp;/将根结点与结点j互换20.i=j;21.j=2*i+1;/被筛结点位于本来结点j的地点22.堆排序堆排序的基本思想是：第一将待排序的记录序列结构成一个堆，此时，选出了堆中所有记录的最大者即堆顶

10、记录，此后将它从堆中移走（平常将堆顶记录和堆中最后一个记录互换），并将节余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。适用文档（1）用大根堆排序的基本思想先将初始文件R1.n建成一个大根堆，此堆为初始的无序区再将重点字最大的记录R1（即堆顶）和无序区的最后一个记录Rn互换，由此获得新的无序区R1.n-1和有序区Rn，且知足R1.n-1.keysRn.key因为互换后新的根R1可能违犯堆性质，故应将目前无序区R1.n-1调整为堆。此后再次将R1.n-1中重点字最大的记录R1和该区间的最后一个记录Rn-1互换，由此获得新的无序区R1.n-2和有序区Rn-1.n，且

11、仍知足关系R1.n-2.keysRn-1.n.keys，相同要将R1.n-2调整为堆。直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作：初始化操作：将R1.n结构为初始堆；每一趟排序的基本操作：将目前无序区的堆顶记录R1和该区间的最后一个记录互换，此后将新的无序区调整为堆（亦称重修堆）。注意：只要做n-1趟排序，选出较大的n-1个重点字即能够使得文件递加有序。用小根堆排序与利用大根堆近似，只可是其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时辰堆排序中无序区老是在有序区以前，且有序区是在原向量的尾部由后往前逐渐扩大至整个向量为止适用文档适用文档代码实现：cppviewpla

12、incopy适用文档/堆排序2.voidHeapSort(intr,intn)4.5.inti;6.inttemp;7.for(i=n/2;i=0;i-)/初始建堆，从最后一个非终端结点至根结点8.Sift(r,i,n);9.for(i=n-1;i0;i-)/重复履行移走堆顶及重修堆的操作11.temp=ri;12.ri=r0;13.r0=temp;14.Sift(r,0,i-1);for(i=0;in;i+)17.coutri;coutn;合并排序二路合并排序基本思想：将若干个有序序列进行两两合并，直至所有待排序记录都在一个有序序列为止。适用文档一路合并算法实现：cppviewplainco

13、py/一次合并2.voidMerge(intr,intr1,ints,intm,intt)5.inti=s;6.intj=m+1;7.intk=s;8.9.while(i=m&j=t)10.11.if(ri=rj)12.r1k+=ri+;/取ri和rj中较小者放入r1k13.else14.r1k+=rj+;15.16.if(i=m)17.while(i=m)/若第一个子序列没办理完，则进行扫尾办理18.r1k+=ri+;19.else20.while(j=t)/若第二个子序列没办理完，则进行扫尾办理适用文档21.r1k+=rj+;22.cppviewplaincopy/一趟合并2.voidMe

14、rgePass(intr,intr1,intn,inth)4.inti=0;5.intk;6.7.while(i=n-2*h)/待合并记录至罕有两个长度为h的子序列9.Merge(r,r1,i,i+h-1,i+2*h-1);10.i+=2*h;适用文档12.if(in-h)13.Merge(r,r1,i,i+h-1,n);/待合并序列中有一个长度小于h14.elsefor(k=i;k=n;k+)/待合并序列中只剩一个子序列15.r1k=rk;/合并排序的非递归算法19.voidMergeSort1(intr,intr1,intn)inth=1;inti;24.while(hn)26.MergePass(r,r1,n-1,h);/合并27.h=2*h;28.MergePass(r1,r,n-1,h);29.h=2*h;for(i=0;in;i+)32.coutri;coutn;下边看看二路合并排序的递归实现适用文档cppviewplaincopy/合并排序的递归算法2.voidMergeSort