[电脑基础知识]归并与基数排序.ppt

* * * * * * 内部排序可能达到的最快速度是什么 若二叉树的高度为 h，则叶子结点的个数不超过 2h-1；反之，若有 u 个叶子结点，则二叉树的高度至少为 ?log2u?+1。即，描述 n个记录排序的判定树上必存在一条长度为 ?log2(n!)? 的路径。 由此得到下述结论：任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为 ?log2(n!)? 。 本章小结 1.深刻理解排序的思想和各种排序方法的特点 2.掌握各种排序方法的时间复杂度的分析方法 3.理解排序方法“稳定”或“不稳定”的含义 4.希尔排序、快速排序、堆排序、归并排序和基数排序等高效方法是本章的学习重点和难点 内部排序的习题 1. 已知序列{ 10，18，4，3，6，12，1，9，18，8 } 请给出采用快速排序、堆排序和归并排序、基数排序对该序列作升序排序时的每一趟结果。 2. 设计一个用单链表作存储结构的选择排序算法。 3. 试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。) 例:设计一个用单链表作存储结构的选择排序算法 void select ( node *head ){ node *p, *q, *min; int temp; p = head; while(p!=NULL) { min=p; q=p-next; while(q!=NULL) { if ( q-key min-key ) min=q; q=q-next; } temp=p-key; p-key=min-key; min-key=temp; p=p-next; } } 例：试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。) void dbubblesort(sqlist r,int n){ int i,j,flag; flag=1; i=1; while ( flag!=0 ) { flag=0; for(j=i; j≤n-i; j++) if (r[j]r[j+1]){ flag=1; r[0]=r[j]; r[j]=r[j+1]; r[j+1]=r[0];} for(j=n-i; ji; j--) if (r[j]r[j-1]){ flag=1; r[0]=r[j]; r[j]=r[j-1]; r[j-1]=r[0];} i++; } //while } * * * * * * * * * * * * * * * * * * * * * * * * * * * 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 10.5 归并排序 归并就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。 采用归并的思想进行排序—归并排序。 假设初始序列含有 n个记录，则可看成是 n个有序的子序列；每个子序列的长度为 1，然后两两归并，得到 ?n/2? 个长度为 2 或 1 有序的子序列，再两两归并，... 如此重复，直至得到一个长度为 n 的有序序列为止。这种排序方法称为 2-路归并。 例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。 21 25 25* 93 62 72 08 37 16 54 49 21 25 25* 49 62 93 08 72 16 37 54 16 37 54 21 25 25* 49 08 62 72 93 08 21 25 25* 49 62 72 93 08 16 21 25 25* 37 49 54 62 72 93 len=1 len=2 len=4 len=8 len=16 16 37 54 整个归并排序仅需 ?log2n ? 趟 ?void Merge(RcdType SR[ ]，RcdType TR[ ]，int i，int m，int n) { //将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]????for(j=m+1，k=i; i=m j=n；++k){ //将SR中记录由小到大并入TR?????? if LQ(SR[i].key，SR[j].key) TR[k]=SR[i+