《c语言各种排序法详解》由会员分享，可在线阅读，更多相关《c语言各种排序法详解（8页珍藏版）》请在金锄头文库上搜索。
1、一插入排序1.1直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列 中，直到全部记录排好序。图解：代码实现：cppview plaincopy1. /直接顺序排序2. voidInsertSort(intr,intn)3. 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. 1.2希尔排序基本思想是：先将整个待排序记录
2、序列分割成若干个子序列，在在序列内分别进行直接 插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。图解：代码实现：cppview plaincopy1. /希尔排序2. voidShellSort(intr,intn)3. 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. 17. for(i=1;in;i+)18. coutri;19. cout”n”；20. 交换排
3、序两两比较相邻记录的关键码,起泡排序是交换排序中最简单的排序方法，其基本思想是: 如果反序则交换，直到没有反序的记录为止。图解：代码实现：cpp view plaincopy1. /起泡排序2. voidBubbleSort(intr,intn)3. 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. 1
4、5. temp=rj;16. 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快速排序基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比 另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个 排序过程可以递归进行，以此达到整个数据变成有序序列。图解：代码实现：cpp view plaincopy1. /快速排序一次划分2. intPartition(intr,intfir
5、st,intend)3. 4. inti=firs t;/初始化5. intj=end;6. inttemp;7. while(ij)8. 9. while(ij&ri=rj)10. j-;/右侧扫描11. if(ij)12. 13. temp=ri;/将较小记录交换到前面14. ri=rj;15. rj=temp;16. i+;17. 18. while(ij&ri=rj)19. i+;/左侧扫描20. if(ij)21. 22. temp=rj;23. rj=ri;24. ri= temp;/将较大记录交换到后面25. j-;26. 27. 28. returni;/i为轴值记录的最终位置
6、29. 30. /快速排序31. voidQuickSort(intr,intfirst,intend)32. 33. if(firstend)34. /递归结束35. intpivot=Partition(r,first,end);/一次划分36. QuickSort(rfirst,pivot-1);/递归地对左侧子序列进行快速排序37. QuickSort(r,pivot+1,end);/递归地对右侧子序列进行快速排序38. 39. 三选择排序31简单选择排序基本思想:设所排序序列的记录个数为n。取1,2,., n-1,从所有n-i+1个记录(Ri,Ri+1,.,R n) 中找出排序码最小
7、的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。图解：代码实现：cpp view plaincopy1. /简单选择排序2. voidSelectSort(intr,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=rindex;18.
8、rindex=temp;19. 20. 21. for(i=0;in;i+)22. coutri”；23. coutn;24. 3.2堆排序堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根 堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称 为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者, 称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉 堆（BinaryHeap），类似地可定义k叉堆。假设当前要筛选结点的编
9、号为k,堆中最后一个结点的编号为m,并且结点k的左右子树 均是堆（即rk+1 rm满足堆的条件），则筛选算法用伪代码可描述为：具体的筛选代码如下：cpp view plaincopy1. /筛选法调整堆2. voidSift（intr,intk,intm）3. 4. inti;5. intj;6. inttemp;7. i=k;8. j=2*i+1;/置i为要筛的结点，j为i的左孩子9. while（j=m）/筛选还没有进行到叶子10. 11. if（jm&rjrj）break;/根结点已经大于左右孩子中的较大者14. else15. 16. temp=ri;17. ri=rj;18. rj=
10、 temp;/将根结点与结点j交换19. i=j;20. j=2*i+1;/被筛结点位于原来结点j的位置21. 22. 23. 堆排序堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记 录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换）,并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记 录为止。（1）用大根堆排序的基本思想 先将初始文件R仁n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1（即堆顶）和无序区的最后一个记录Rn交换，由此得到 新的无序区 R1.n-1和有序区 Rn，且满足 R1.n
11、-1.keysSRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再 次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新 的无序区 R1.n-2和有序区 Rn-1.n，且仍满足关系 R1.n-2.keys=0;i-)/初始建堆，从最后一个非终端结点至根结点7. Sift(r,i,n);8. for(i=n-1;i0;i-)/重复执行移走堆顶及重建堆的操作9. 10. temp=ri;11. ri=r0;12. r0=temp;13. Sift(r,0,i-1);14. 15. for(i=0;in;i+)16. coutri;17. coutn;18. 归并排二路归并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。一路归并算法实现：cppview plaincopy1. /一次归并2. voidMerge(intr,intr1,ints,intm,intt)3. 4. inti=s;5. intj=m+1;6. intk=s;7. while(i=m&j=t)8. 9. if(ri=rj)10. r1k+=ri+;/取 ri和 rj中较小者放入 r1k11. else12. r1k+
