c语言各种排序法详解.docx

《c语言各种排序法详解.docx》由会员分享，可在线阅读，更多相关《c语言各种排序法详解.docx（22页珍藏版）》请在三一文库上搜索。

1、最新 料推荐一插入排序1.1直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。图解：代码实现：cppview plaincopy1. / 直接顺序排序2.voidInsertSort(intr,intn)3. 4. for ( int i=2; in; i+)1最新 料推荐5. 6.r0=ri;/设置哨兵7.for ( int j=i-1; r0rj; j-)/寻找插入位置8.rj+1=rj;/记录后移9. rj+1=r0;10. 11. for ( int k=1;kn;k+)12.coutrk ;13.coutn;14.1.2

2、 希尔排序基本思想是： 先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。图解：代码实现：cppview plaincopy1./ 希尔排序2.void ShellSort(int r,int n)3. 4. int i;2最新 料推荐5. int d;6. int j;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 (

3、i=1;in;i+)18.coutri ;19.coutn;20. 二 交换排序2.1 起泡排序起泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。图解：3最新 料推荐代码实现：cppview plaincopy1./ 起泡排序2.void BubbleSort(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.

4、 bound=exchange;11. exchange=0;12.for( int j=0; jrj+1)14. 4最新 料推荐15. temp=rj;16. rj=rj+1;17. rj+1=temp;18.exchange=j;/ 记录每一次发生记录交换的位置19. 20. 21. for ( int i=0;in;i+)22.coutri ;23.coutn;24.2.2 快速排序基本思想 :通过一趟 排序 将要排序的 数据分割 成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数

5、据变成有序序列。图解：5最新 料推荐代码实现：cppview plaincopy1. / 快速排序一次划分2.intPartition(intr,intfirst,intend)3. 4.inti=first;/ 初始化5.intj=end;6最新 料推荐6. int temp;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

6、(ij)22. 23. temp=rj;24. rj=ri;25.ri=temp;/ 将较大记录交换到后面26.j-;27. 28. 29.returni;/i为轴值记录的最终位置30. 31.32. / 快速排序33.voidQuickSort(intr,intfirst,intend)34. 35. if (firstend)36./递归结束37.int pivot=Partition(r, first, end);/ 一次划分38.QuickSort(r, first, pivot-1);/递归地对左侧子序列进行快速排序39.QuickSort(r, pivot+1, end);/递归地

7、对右侧子序列进行快速排序40. 41.42. 三 选择排序7最新 料推荐3.1 简单选择排序基本思想： 所排序序列的 个数 n。i取 1,2, ,n-1, 从所有 n-i+1 个 （ Ri,Ri+1, ,Rn）中找出排序 最小的 ，与第i 个 交 。 行n-1 趟后就完成了 序列的排序。 解：代 ：cppview plaincopy1. / 简单选择排序2.voidSelectSort(intr ,intn)3. 4. int i;5. int j;6. int index;7. int temp;8最新 料推荐8.for(i=0; in-1; i+)/ 对 n 个记录进行 n-1 趟简单选择

8、排序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 堆排序堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆 ）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆 ）。大根堆和小根堆： 根结点 （亦称为堆顶） 的关键字 是

9、堆里所有结点关键字中最小者的堆称为小根堆，又称 最小堆 。根结点（亦称为堆顶）的 关键字 是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆（ BinaryHeap ），类似地可定义k 叉堆。9最新 料推荐假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点 k 的左右子树均是堆（即rk+1 rm 满足堆的条件），则筛选算法用伪代码可描述为：具体的筛选代码如下：cppview plaincopy1. / 筛选法调整堆2.voidSift(intr,intk,intm)10最新 料推荐3. 4.5. int i;6. int

10、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. 堆排序堆排序的基本思想是： 首先将待排序的记录序列构造成一个堆， 此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记

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

12、足关系 R1.n- 2.keysRn-1.n.keys ，同样要将 R1.n-2 调整为堆。11最新 料推荐直到无序区只有一个元素 止。（2 ）大根堆排序算法的基本操作： 初始化操作：将R1.n 构造 初始堆； 每一趟排序的基本操作：将当前无序区的堆 R1 和 区 的最后一个 交 ，然后将新的无序区 整 堆（亦称重建堆）。注意：只需做 n-1 趟排序， 出 大的 n-1 个关 字 即可以使得文件 增有序。用小根堆排序与利用大根堆 似， 只不 其排序 果是 减有序的。 堆排序和直接 排序相反：在任何 刻堆排序中无序区 是在有序区之前， 且有序区是在原向量的尾部由后往前逐步 大至整个向量 止12最

13、新 料推荐13最新 料推荐代码实现：cppview plaincopy14最新 料推荐1. / 堆排序2.voidHeapSort(intr ,intn)3. 4.5. int i;6. int temp;7.for(i=n/2; i=0; i-)/ 初始建堆，从最后一个非终端结点至根结点8. Sift(r, i, n) ;9.for(i=n-1; i0; i-)/ 重复执行移走堆顶及重建堆的操作10. 11. temp=ri;12. ri=r0;13. r0=temp;14. Sift(r, 0, i-1);15. 16. for (i=0;in;i+)17.coutri ;18.coutn

14、;19. 四 归并排序二路归并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。15最新 料推荐一路归并算法实现：cppview plaincopy1. / 一次归并2.voidMerge(intr,intr1,ints,intm,intt)3. 4.5. int i=s;6. int j=m+1;7. int k=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)/ 若第

15、一个子序列没处理完，则进行收尾处理18. r1k+=ri+;19. else20.while(j=t)/ 若第二个子序列没处理完，则进行收尾处理21. r1k+=rj+;16最新 料推荐22.cppview plaincopy1. / 一趟归并2.voidMergePass(intr ,intr1 ,intn,inth)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. if (in-h)17最新 料推荐13.

16、Merge(r, r1, i, i+h-1, n);/待归并序列中有一个长度小于h14.else for (k=i; k=n; k+)/待归并序列中只剩一个子序列15. r1k=rk;16. 17.18. / 归并排序的非递归算法19.voidMergeSort1(intr ,intr1 ,intn )20. 21. int h=1;22. int i;23.24. while (hn)25. 26.MergePass(r, r1, n-1, h);/ 归并27. h=2*h;28. MergePass(r1, r, n-1, h);29. h=2*h;30. 31. for (i=0;in;

17、i+)32.coutri ;33. cout n ;34. 下面看看二路归并排序的递归实现18最新 料推荐cppview plaincopy1. / 归并排序的递归算法2.voidMergeSort2(intr,intr1,intr2,ints,intt)3. 4.5. int m;6. if (s=t)7. 8. r1s=rs;9.10.11.else12.13.m=(s+t)/2;14.MergeSort2(r, r2, r1, s, m);/ 归并排序前半个子序列15.MergeSort2(r, r2, r1, m+1, t);/ 归并排序后半个子序列16.Merge(r2, r1, s, m, t);/ 将两个已排序的子序列归并19最新 料推荐17. 18. 总结各种排序方法的比较（未完待续）：20