数据结构课件10

1、第十章第十章 排序排序精英专升本精英专升本10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 9710.1 概概 述述若整个排序过程不需要访问外存不需要访问外存便能完成，则称此类排序问

2、题为内部排内部排序序； 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序外部排序。内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区52, 49, , 36, 14, 58, 61, 23, , 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 规则不同规则不同时间复杂度不同时间复杂度不同10.2 10.2 插入排序插入排序每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小，插入插入到前面

3、到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上上，直到，直到对象全部插入为止。对象全部插入为止。有序序列R1.i-1Ri无序序列 Ri.n直接插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n利用 “顺序查找顺序查找”实现“在R1.i-1中查找查找Ri的插入位置”排序过程：整个排序过程为排序过程：整个排序过程为n-1n-1趟插入，即先将序列中趟插入，即先将序列中第第1 1个记个记录录看成是一个有序子序列，然后从看成是一个有序子序列，然后从第第2 2个记录个记录开始，开始，逐个逐个进行插进行插入，直至整个序列有序入，直至整个序列有序。【13】, 6, 3, 31,

4、9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 0 1 2 3 4 5 6254925*1608初态：初态：将序列存入顺序表将序列存入顺序表L L中，将中，将L.r0L.r0作为哨兵作为哨兵* *表示后一个表示后一个2525从Ri-1起向前进

5、行顺序查找， R0 = Ri; / 设置“哨兵”循环结束表明Ri的插入位置为 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 从后往前找j=i-1插入位置插入位置 对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1插入位置插入位置令 i = 2，3，, n, 实现整个序列的排序。for ( i=2; i=n; +i ) void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插

6、入排序。 / InsertSortL.r0 = L.ri; / 复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移L.rj+1 = L.r0; / 插入到正确位置实现内部排序的基本操作基本操作有两个：（2）“移动移动”记录。（1）“比较比较”序列中两个关键字的 大小；n-1 比较次数比较次数移动次数移动次数最好情况下：最好情况下：每趟只需比较每趟只需比较 1 次，不移动次，不移动 总比较次数为总比较次数为 n-1for(i=2;i=L.length;+i) if( L.ri.keyL.ri-1.key)最坏情况下：

7、第最坏情况下：第 i i 趟比较趟比较i i次，移动次，移动i+1i+1次次2) 1)(2(2nnini比较次数比较次数2) 1)(4() 1(2nnini移动次数移动次数if( L.ri.keyL.ri-1.key) L.r0=L.ri; / 复制为哨兵复制为哨兵 L.rj+1=L.r0; /插入到正确位置插入到正确位置 若出现各种可能排列的概率相同，则可取最好情况若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况和最坏情况的平均情况 平均情况平均情况比较次数比较次数和和移动次数移动次数为为n n2 2/4/4时间复杂度为时间复杂度为 o(o(n n2 2) )空间复杂度为空间

8、复杂度为 o(1)是一种是一种稳定稳定的排序方法的排序方法0 1 2 3 4 5 因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找折半查找实现“在R1.i-1中查找查找Ri的插入位置”，如此实现的插入排序为折半插折半插入入排序。二、折半插入排序二、折半插入排序212549251608lowhighi=2212549251608lowhighmi=3212549251608lowhighm212549251608low/mhighi=4212549251608lowhighm212549251608low/mhighi=5212549251608lowhighm2125492

9、51608lowhighmi=62 12 54 92 51 60 8void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移L.r = L.r0; / 插入low = 1; high = i-1;while (low0)&(flag=1) flag=0; for(j=1;jL.rj+1.key) flag=1; x=L.rj;L.rj=L.rj+1;L.rj+1=x; 最好情况下：最好

10、情况下：)(21)(211nninni)(23)(321nninni时间复杂度为时间复杂度为 o(o(n n2 2) )空间复杂度为空间复杂度为 o(1)是一种是一种稳定稳定的排序方法的排序方法需需 n-1趟排序，趟排序，第第i趟比较趟比较n-i次，移动次，移动3(n-i)次次最坏情况下：最坏情况下：基本思想：基本思想：任取一个元素任取一个元素 ( (如第一个如第一个) ) 为中心为中心所有比它所有比它小小的元素一律前放，比它的元素一律前放，比它大大的元素一律的元素一律后放，形成后放，形成左右两个子表左右两个子表；对各子表重新选择对各子表重新选择中心中心元素并依此规则调整，直元素并依此规则调整

11、，直到每个子表的元素到每个子表的元素只剩一个只剩一个目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大于枢轴关键字大于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)。52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进

12、行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow 可见，经过“一次划分一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = R

13、low.key; / 枢轴 while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 从左向右搜索Rhigh = Rlow;Rlow = R0; return low; 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序void QSort (RedType &

14、 R, int s, int t ) / 对记录序列Rs.t进行快速排序 if (s t-1) / 长度大于1 / QSortpivotloc = Partition(R, s, t); / 对 Rs.t 进行一次划分一次划分 / 对低子序列递归排序，pivotloc是枢轴位置是枢轴位置 / 对高子序列递归排序void QuickSort( SqList & L) / 对顺序表进行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。可以证明，平均计算时间是可以证明，

15、平均计算时间是O(nlog2n)。实验结果表明：就实验结果表明：就平均计算时间平均计算时间而言，快速排序是我而言，快速排序是我们所讨论的所有内排序方法中们所讨论的所有内排序方法中最好最好的一个的一个。快速排序是递归的，需要有一个栈存放每层递归调用快速排序是递归的，需要有一个栈存放每层递归调用时参数时参数（新的（新的lowlow和和highhigh）。最大递归调用层次数与递归树的深度一致，因此，要最大递归调用层次数与递归树的深度一致，因此，要求存储开销为求存储开销为 O(log2n) 。最好：划分后，左侧右侧子序列的最好：划分后，左侧右侧子序列的长度相同长度相同最坏：从小到大排好序，最坏：从小到

16、大排好序，递归树成为单支树递归树成为单支树，每次，每次划分只得到一个比上一次少一个对象的子序列，必划分只得到一个比上一次少一个对象的子序列，必须经过须经过 n n-1 -1 趟才能把所有对象定位，而且第趟才能把所有对象定位，而且第 i i 趟趟需要经过需要经过 n n- -i i 次关键码比较才能找到第次关键码比较才能找到第 i i 个对象个对象的安放位置的安放位置2121211nnninni)()(时间效率：时间效率：O(nlog2n) 每趟确定的元素呈指数增加每趟确定的元素呈指数增加空间效率：空间效率：O（log2n）递归要用到栈空间递归要用到栈空间稳稳 定定 性：性： 不稳定不稳定 可选

17、任一元素为支点。可选任一元素为支点。10.4 10.4 选择排序选择排序每一趟在后面每一趟在后面 n-i +1个中选出关键码最小的对象个中选出关键码最小的对象, 作作为有序序列的第为有序序列的第 i 个记录个记录简简 单单 选选 择择 排排 序序堆堆 排排 序序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n最小者最小者最小者最小者最小者最小者0 1 2 3 4 5最小者最小者最小者最小者结果结果各趟排序后的结果各趟排序后的结果简单选择排序的算法描述如下：void SelectSo

18、rt (Elem R, int n ) / 对记录序列R1.n作简单选择排序。 for (i=1; i0; -i ) / 建大顶堆for ( i=H.length; i1; -i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互交换 / 对 H.r1 进行筛选如何如何“建堆建堆”？两个问题两个问题:如何如何“调整调整”？typedef SqList HeapType; / 堆采用顺序表表示之 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210思考：有思考：有n 个结点的完全二叉树

19、采用顺序个结点的完全二叉树采用顺序存储，最后一个分支结点的标号是多少？存储，最后一个分支结点的标号是多少？从第从第 n/2 个元素起，至第一个元素止，进行反复个元素起，至第一个元素止，进行反复筛选筛选堆堆 30 1 60 240 4 70 5 8 3 12 610 7 1 2 3 4 5 6 7 3060 840701210 30 1 60 240 4 70 510 7 1 2 3 4 5 6 7 3060 840701210无序序列建成堆无序序列建成堆1 8 12 3 6 30 1 60 240 4 70 5 12 810 7 1 2 3 4 5 6 7 3060124070810无序序列建

20、成堆无序序列建成堆1 3 6 30 1 6040 4 12 810 7 1 2 3 4 5 6 7 3060124070810无序序列建成堆无序序列建成堆2 3 6 2 70 5 30 1 7040 4 12 810 7 1 2 3 4 5 6 7 3070124060810无序序列建成堆无序序列建成堆2 3 6 2 60 5 7040 4 12 810 7 1 2 3 4 5 6 7 3070124060810无序序列建成堆无序序列建成堆3 3 6 2 60 5 30 1 3040 4 12 810 7 1 2 3 4 5 6 7 7030124060810无序序列建成堆无序序列建成堆3 3

21、 6 2 60 5 70 1 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810无序序列建成堆无序序列建成堆3 3 6 2 5 70 1 30建堆完毕建堆完毕将根结点将根结点r1与左、右子树根结点比较，并与左、右子树根结点比较，并与小者与小者交换交换重复重复直至叶子结点，得到新的堆直至叶子结点，得到新的堆交换交换r1和和rn后，如何将后，如何将r1.n-1重新调整，重新调整，使之成使之成为新堆？为新堆？ 6040 4 12 810 7 1 2 3 4 5 6 7 7060124030810 3 6 2 30 5 70 1堆的重新调整堆的重新调整1堆的重新调整

22、堆的重新调整1 6040 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 510 17060124030810707010 60106010104040堆的重新调整堆的重新调整2 4010 4 12 810 7 1 2 3 4 5 6 7 3 6 2 30 560 160401210308107070 堆的重新调整堆的重新调整2 4010 4 12 6010 7 1 2 3 4 5 6 7 3 6 2 30 58 1840121030601070706060堆的重新调整堆的重新调整2 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 140

23、3012108601070706060堆的重新调整堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 540 1403012108601070706060堆的重新调整堆的重新调整3 3010 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 1830121086010707060604040堆的重新调整堆的重新调整3 108 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 530 1301012886010707060604040堆的重新调整堆的重新调整4 108 4 12 6010 7 1 2 3 4 5 6 7

24、 3 6 28 530 1301012886010707060604040堆的重新调整堆的重新调整4 1030 4 12 6010 7 1 2 3 4 5 6 7 3 6 28 58 18101230860107070606040403030堆的重新调整堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 512 11210830860107070606040403030堆的重新调整堆的重新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新调整堆的重

25、新调整5 1030 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 58 18108308601070706060404030301212堆的重新调整堆的重新调整5 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 510 11088308601070706060404030301212堆的重新调整堆的重新调整6 830 4 8 6010 7 1 2 3 4 5 6 7 3 6 28 5

26、8 18883086010707060604040303012121010时间效率：时间效率：O(nlogO(nlog2 2n) n) 空间效率：空间效率：O O（1 1）稳稳 定定 性：性：不稳定不稳定适用于适用于n 较大较大的情况的情况已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用建小根堆，请画出建堆的过程。 10.5 10.5 归并排序归并排序归并：将两个或两个以上的有序表组合成一个新有序表归并：将两个或两个以上的有序表组合成一个新有序表 排序过程排序过程初始序列看成初始序列看成n个个有序子序列，每个子序列长度为有序子序列，每个子序列长度

27、为1两两合并两两合并，得到，得到 n/2 个长度为个长度为2或或1的有序子序列的有序子序列再两两合并，重复直至得到再两两合并，重复直至得到一个一个长度为长度为n的有序序的有序序列为止列为止0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0

28、 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776

29、780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680B B 表的元素都表的元素都已移入已移入 C C 表，表，只需将只需将 A A 表的表的剩余部分移入剩余部分移入 C C 表即可表即可0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965768097例例初始关键字：初始关键字： 49 38 65 97 76

30、13 27一趟归并后：一趟归并后： 38 49 65 97 13 76 27二趟归并后：二趟归并后： 38 49 65 97 13 27 76三趟归并后：三趟归并后： 13 27 38 49 65 76 97时间效率：时间效率：O(nlogO(nlog2 2n) n) 空间效率：空间效率：O O（n n）稳稳 定定 性：性：稳定稳定10.6 10.6 基数排序基数排序对对5252张扑克牌按以下次序排序：张扑克牌按以下次序排序： 22 33 AA 22 33 AA 22 33 AA 22 33 A A两个关键字：花色（两个关键字：花色（ ） 面值（面值（2323AA）并且并且“花色花色”地位高于

31、地位高于“面值面值”多关键字排序多关键字排序链式基数排序链式基数排序链式基数排序：用链式基数排序：用作存储结构的基数排序作存储结构的基数排序先对先对最高位最高位关键字关键字k1k1（如花色）排序，将序列分如花色）排序，将序列分成若干子序列，每个子序列有相同的成若干子序列，每个子序列有相同的k1k1值；值；然后让每个子序列对然后让每个子序列对次关键字次关键字k2k2（如面值）排序如面值）排序，又分成若干更小的子序列；，又分成若干更小的子序列；依次重复，直至就每个子序列对依次重复，直至就每个子序列对最低位关键字最低位关键字kdkd排序排序，就可以得到一个有序的序列。，就可以得到一个有序的序列。27

32、8,109,063,930,184,589,269,008,083按百位排序008,063,083269,278589930109,184按个位排序008063083109184269278589930十位十位278，109，063，930，184，589，269，008，083按个位排序930，063，083，184，278，008，109，589，269按十位排序008，109，930，063，169，278，083，184，589按百位排序008，063，083，109，169，184，278，589，930，最低位优先法最低位优先法 知道各级关键字的知道各级关键字的主次关系主次关系 知

33、道各级关键字的知道各级关键字的取值范围取值范围链式基数排序链式基数排序 首先对首先对低位关键字低位关键字排序，各个记录按照此位关键字排序，各个记录按照此位关键字的值的值分配分配到相应的序列里。到相应的序列里。 按照序列对应的值的大小，从各个序列中将记录按照序列对应的值的大小，从各个序列中将记录收集收集，收集后的序列按照此位关键字有序。，收集后的序列按照此位关键字有序。 在此基础上，对前一位关键字进行排序。在此基础上，对前一位关键字进行排序。初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3

34、e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集一趟收集008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5

35、e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集二趟收集 设置设置1010个队列个队列，fifi和和eiei分别头指针和尾指针分别头指针和尾指针对最低位关键字（个位）进行，改变记对最低位关键字（个位）进行，改变记录的指针值，录的指针值，将链表中记录分配至将链表中记录分配至1010个链队列中个链队列中，每个队列记录的关键字的个位相同每个队列记录的关键字的个位相同是改变所有非空队列的是改变所有非空队列的域，令其指向域，令其指向，重新将重新将1010个队列链成一个链表个队列链成一个链表