c语言各种排序法详解

1、实用文档1.1插入排序直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中, 直到全部记录排好序。图解:/十I 无序区屮s-l肓接插入排库的基本思想图網+初始龍值帛列121592063124-Lj第一趟排序结果1212063124第二趟排序结果1 %2063124Lj第二趟排序结果1520631*bs_丁 F:1第四植排序结果6-49*1215203124+L i第五趟排序结果69121?20却1p第六趟排序结果69121520*2431 Q图Z自接插入排序过程示卧代码实现：cppview pla incopy1./直接顺序排序2.void Insert

2、Sort( int r,intn)3.4.for (int i=2; in;i+)5.6.r0=ri;/设置哨兵7.for (intj=i-1;r0vrj;j-)/寻找插入位置8.rj+1=rj;/记录后移9. rj+1=r0;10. 11. for (int k=1;kn;k+)12. cout/希尔排序2.voidShellSort( int r,int n)3.4.inti；5.intd;6.intj；7.for(d=n/2;d=1;d=d/2)/以增量为d进行直接插入排序8.9.for(i=d+1;ivn; i+)10.11.rO=ri;/暂存被插入记录12.for (j=i-d;j0

3、&r0vrj;j=j-d)13.rj+d=rj;/记录后移d个位置14.rj+d=rO;15.16.17.for (i=1;i二交换排序2.1起泡排序两两比较相邻记录的关键码，起泡排序是交换排序中最简单的排序方法，其基本思想是: 如果反序则交换，直到没有反序的记录为止。图解:反序则交换+r p r-t-i rt-i 芟 W rji-i W 加珀区育屋区屮已经位T最纽靖十图誌4起泡排库的基本思想图昭初始鰹值摩列50135597273849C5第一趙排序结杲13刃L L227334965必第二蠲排慝结果13SO273&49556597+J第三趟排序结杲1327334V50556597第四趙排序结果

4、!327鹑4950556597+gS-5起泡排序过程示例代码实现：cppview pla incopy1./ 起泡排序2.voidBubbleSort( int r,int n)3.4.int temp;5.int exchange;6.int bound;7.exchange=n-1;排序的范围是r0到rn-18.while (exchange)序有记录交换才进行本趟排序9.10.bound=exchange;11.exchange=0;12.for (int j=0; jvbound; j+)13.if (rjrj+1)14./第一趟起泡/仅当上一趟排/ 一趟起泡排序/记录每一15.tem

5、p=rj;16.rj=rj+1;17.rj+1=temp;18.exchange=j;次发生记录交换的位置19.20.21.for (int i=0;in;i+)22.coutvrivv 23.cout n;24.2.2快速排序基本思想：通过一趟 排序将要排序的 数据分割成独立的两部分，其中一部分的所有数据都比 另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以 递归进行，以此达到整个数据变成有序序列。图解:In diu 厂冋虫卜 tV均孤 铀值均沁位于最饕位養圏卜百快应排莒的基范恿想亟解屮初怕键值序列231363115)2弘右侧扫描！ 2S23, j

6、前移一位2313496311928+iJit194%咽与顼胶撫191349631232&J冲if诟移一位，：隹畚左側扫堀1913496312328*ij片1X2九躺移一位19136312324423,巾与交换 19 L3 23 6 31 49 28屮i1M箭移一位、准备右删扫播 旳 B 13疔51 49 血1i!3123i移一位 15 B 1.35 3149 血f ie23,町与明交换19 13 52Jj?3149 珈h4j 1循移一位刁一次划分结束U9 13 6 23 C31 49 28 +训J图gY ：矢划井的过程示例b丽僦丽列2313 49 311928PL廣划分之后19 13 C 23

7、492S1屮b分别进行快融區&13 I)6【13卩13苗】31【491屮L29-y最终结果6 B 19 茁2S314如圈卜g快谨排序的迥程示例、t代码实现：cppview pla incopy1. /快速排序一次划分2. int Partition( int r, int first, int end)3. 4.int i=first;/初始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.

8、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;值记录的最终位置30.31.32./快速排序33.void QuickSort( first,int34.35.if (firstvend)36./递归结束37.intpivot=Partition(r,38.QuickSort(r,first,速排序39.QuickSort(r,pivot+1,快速排序end)first,pivot-1);end);40./右/将较小记/左/将较大记

9、i为轴/end); / 一次划分/递归地对左侧子序列进行快/递归地对右侧子序列进行41.42. 三选择排序3.1简单选择排序个记录n-1趟基本思想：设所排序序列的记录个数为n。i取1,2,n-1,从所有n-i+1(Ri,Ri+1,Rn)中找出排序码最小的记录，与第i个记录交换。执行后就完成了记录序列的排序。图解:有再区无序区心已经位于最繽位置加伪孟序区的最小记录a囹 宀 直单他择却圧耳甚$岂拦图解瞬健值删4927197761338 P第趙排厚结果132765Q776493S心第二趙排序结果1327i 659771549Pl #第二葩排扇结果13273曲760J P第四趟排库结果13273849

10、&97第五趟排呼錨果13273S49(S5&7 76 +13273S496576-3-肯单选墀排序的过程示例屮代码实现：cppview pla incopy1./简单选择排序2.void SelectSort( int r , intn)3.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=

11、rindex;18.rindex=temp;19.20.21.for(i=0;in;i+)22.coutrivv ;23.cout n;24.3.2堆排序堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（ 大根堆）。大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为 小根堆，又称 最小堆。根结点（亦称为堆顶）的 关键字是堆里所有结点关键字中最大者，称 为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆（BinaryHeap），类似地可定义 k叉堆。Mu

12、 1邛茲1创7 |131加zdis264726+J何大撮堆型对应的序列门小很堆廖对应的肠卜难的示例Q假设当前要筛选结点的编号为k,堆中最后一个结点的编号为m并且结点k的左右子树均是堆（即rk+1 rm满足堆的条件），则筛选 算法用伪代码可描述为:J/1-iSK分别指向当前要筛选的结卓和要筛选绪点的左孩子2 “7 z若结点L已杲叶子则筛选完毕否则，比態筛选结点的左右孩子结点（如果有右按子并将j指冋关键码较大的结昴3.将要筛选结点L的关键码与i所指向的绪点的并键码进行比較界3 1如果结点L的关锂码大则完全二更树麗是堆，筛迭完毕.屮 王？否则将咽与如交换5转步骚2缮谢亍筛选F p具体的筛选代码如下:

13、cppview pla incopy1./筛选法调整堆2.void Sift( intr,intk, int m)3.4.5.int i;6.int j;7.int temp;8.i=k;9.j=2*i+1;/置i为要筛的结点，j为i的左孩子10.while (j=m)/筛选还没有进行到叶子11.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.23.24.堆排序堆排序的基本思想是： 首先将待

14、排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录， 以此类推，直到堆中只有一个记录为止。(1)用大根堆排序的基本思想 先将初始文件 R1.n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区 R1.n-1 和有序区 Rn，且满足 R1.n-1.keys Rn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R仁n-1调整为堆。然后再次将R仁n-1中关键字最大的记录R1和该区间的最后一

15、个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系 R1.n-2.keys =0;i-)个非终端结点至根结点8.Sift(r,i, n);9.for (i=n-1;i0;i-)及重建堆的操作10.11.temp=ri;12.ri=r【O；13.r0=temp;14.Sift(r,0,i-1);15.16.for (i=0;in;i+)17.coutrivv ;18.coutvv n;19.n)/初始建堆，从最后一/重复执行移走堆顶四归并排序二路归并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。第一趟排序结果+第二趙排序结果

16、第三趟排序結果70 8-1S二貉归并的排序过程示例一路归并算法实现:cppview pla incopy1./ 一次归并2.void Merge(int r,int r1,int s, int m, int t)3.4.5.inti=s;6.intj=m+1;7.intk=s;8.9.while (i=m& jv=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.whil

17、e (jn-h-1 It况示意园cpp view pla incopy1./ 一趟归并2.void MergePass(int r ,int r1, int n, int h)3.4.int i=0;5.int k;6.7.while (i=n-2*h)/待归并记录至少有两个长度为h的子序列8.9.Merge(r, r1, i,i+h-1,i+2*h-1);10.i+=2*h;11.12.13.if (in-h)Merge(r,度小于hr1, i,i+h-1,n);/待归并序列中有一个长14.else for (k=i;k=n;k+)/待归并序列中只剩一个子序列15.r1k=rk;16.17.18./归并排序的非递归算法19.voidMergeSort1( intr,int r1, int n )20.21.int h=1;22.int i;23.24.while (hn)25.26.MergePass