《数据结构排序》由会员分享，可在线阅读，更多相关《数据结构排序（46页珍藏版）》请在金锄头文库上搜索。
1、第1页数据结构(C+语言版)第2页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第3页 排序：排序：将数据元素的一个任意序列，重新排列成一个将数据元素的一个任意序列，重新排列成一个按关键按关键按关键按关键 字有序字有序字有序字有序的序列。的序列。 概念概念 例：将关键字序列：例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 调整为：调整为：14, 23, 36, 49, 52, 58, 61 , 80 一般情况下，假设含一般情况下，假设含 n 个记录的序列为个记录的序列为 R1, R2, , Rn ， 其相应的关键字
2、序列为其相应的关键字序列为 K1, K2, , Kn R R1 1, , R R2 2, , R R3 3, , R R4 4, , R R5 5, , R R6 6, , R R7 7, , R R8 8 K K1 1, , K K2 2, , K K3 3, , K K4 4, , K K5 5, , K K6 6, , K K7 7, , K K8 8 这些关键字相互之间可以进行比较，即在它们之间存在着这这些关键字相互之间可以进行比较，即在它们之间存在着这 样一个关系样一个关系(在次讨论升序在次讨论升序在次讨论升序在次讨论升序) ： Kp1Kp2KpnKp1 Kp2 Kp3 Kp4 Kp
3、5 Kp6 Kp7 Kp8 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, , Rpn 的操作称作的操作称作排序排序排序排序。Rp1, Rp2, Rp3, Rp4, Rp5, Rp6, Rp7, Rp8 第4页 若若 Ki 为记录为记录 Ri 的的主主主主关键字，则排序关键字，则排序结果惟一结果惟一结果惟一结果惟一。 若若 Ki 为记录为记录 Ri 的的次次次次关键字，则排序关键字，则排序结果结果结果结果可以可以不惟一不惟一不惟一不惟一（因为（因为 会有相同的关键字）。会有相同的关键字）。 例：例：设排序前的关键字序列为：设排序前的关键字序列为：5
4、2, 49, 80, 36, 14, 58, 3636, 23 若排序后的关键字序列为：若排序后的关键字序列为：14, 23, 36, 3636, 49, 52, 58, 80， 则则排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的。 若排序后的关键字序列为：若排序后的关键字序列为：14, 23, 3636, 36, 49, 52, 58, 80， 则则排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的。 第5页 内部排序和外部排序内部排序和外部排序 若若整个排序过程不需要访问外存整个排序过程不需要访问外存便能完成，则称此类排序问便能完成，则称此类排序问
5、题题为内部排序；为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程反之，若参加排序的记录数量很大，整个序列的排序过程不不可能在内存中完成可能在内存中完成，则称此类排序问题，则称此类排序问题为外部排序为外部排序(本章不讨论本章不讨论) 。 内部排序的方法内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列的过程。内部排序的过程是一个逐步扩大记录的有序序列的过程。 有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区经过一趟排序经过一趟排序 第6页排序方法分类：排序方法分类： 1)、插入排序：、插入排序：直接插入排序、折半插入排序、希尔
6、排序直接插入排序、折半插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：、选择排序：简单选择排序、堆排序简单选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 5)、基数排序、基数排序 基于不同的基于不同的“扩大扩大” 有序序列长度的方法，内部排序有序序列长度的方法，内部排序 方法大致可分下列几种类型：方法大致可分下列几种类型： 依次将无序子序列中的一依次将无序子序列中的一 个记录个记录“插入插入插入插入”到有到有 序序列中，序序列中，从而增加记录从而增加记录 的有序子序列的的有序子序列的长度。长度。 通过通过“交换交换交
7、换交换”无序序列中的记录从而无序序列中的记录从而 得到其中得到其中关键字最小关键字最小或或最大最大的记录，并的记录，并 将它将它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。 从记录的无序子序列中从记录的无序子序列中“选择选择选择选择” 关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。 通过通过“归并归并归并归并”两个两个 或两个以上的记录有或两个以上的记录有 序子序列，逐步增加序子序列，逐步增加 记
8、录有序序列的长度。记录有序序列的长度。 基数排序是一种基于多基数排序是一种基于多 关键字排序的思想，将单关关键字排序的思想，将单关 键字按基数分成键字按基数分成 “多关键字多关键字” 进行排序的方法。进行排序的方法。 第7页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第8页插入排序插入排序 一趟直接插入排序的基本思想：一趟直接插入排序的基本思想： 有序序列有序序列 R1 . i -1 Ri无序序列无序序列 Ri . n有序序列有序序列 R1 . i无序序列无序序列 Ri +1 . n实现实现“一趟插入排序一趟插入排序”可分可分三步三步进行：进行
9、： 3将将 Ri 插入（复制）到插入（复制）到 相应相应 的位置上。的位置上。 2记录后移一个位置；记录后移一个位置； 1在在 有序区有序区 中查找中查找 Ri 的插入位置，的插入位置，简单排序方法简单排序方法第9页直接插入排序直接插入排序 初始状态初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849
10、657697132749494938659776132749 3849387 趟趟 排序排序 1 趟趟 排序排序 2 趟趟 排序排序 void InsertSort ( SqList &L ) / 对顺序表对顺序表 L 作直接插入排序。作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 排序过程：排序过程：先将序列中第先将序列中第 1 个记录看成是一个有序子序列个记录看成是一个有序子序列， 然后从第然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。个记录开始，逐个进行插入，直至
11、整个序列有序。 在在 R1. i-1中查找中查找 Ri 的插入位置的插入位置; 对于在查找过程中找到的那些关键字对于在查找过程中找到的那些关键字 不小于不小于 Ri.key 的记录，在查找的同的记录，在查找的同 时实现记录向后移动；时实现记录向后移动； 插入插入插入插入 RRi i ; ;L.r0 = L.ri; / 复制为监视哨复制为监视哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移记录后移 L.r L.r j j + 1 = L.r0; / + 1 = L.
12、r0; / 插入到正确位置插入到正确位置插入到正确位置插入到正确位置 第10页比较次数和移动次数均比较次数和移动次数均约约约约为：为： T(n)=O(n) 算法评价算法评价 时间复杂度：时间复杂度： 比较次数：比较次数： 移动次数：移动次数：0 最好的情况：最好的情况：待排序记录按关键字从小到大排列（正序）待排序记录按关键字从小到大排列（正序） 比较次数：比较次数： 移动次数：移动次数： 最坏的情况：最坏的情况：待排序记录按关键字从大到小排列（逆序）待排序记录按关键字从大到小排列（逆序） 一般情况：一般情况：待排序记录是随机的，取平均值。待排序记录是随机的，取平均值。 空间复杂度：空间复杂度：
13、S(n)=O(1) 直接插入排序是稳定排序直接插入排序是稳定排序 5 4 3 2 1 第11页第二趟希尔排序第二趟希尔排序 第三趟分组，设第三趟分组，设 d3 = 1 希尔排序（缩小增量排序）希尔排序（缩小增量排序） 基本思想基本思想：对待排序列先作对待排序列先作“宏观宏观”调整，再作调整，再作“微观微观”调调整。整。 排序过程排序过程：先取一个正整数先取一个正整数 d1 n，把所有把所有相隔相隔 d1 的记录放的记录放 在一组内，组内进行直接插入排序；然后取在一组内，组内进行直接插入排序；然后取 d2 d1，重复上述分重复上述分 组和排序操作；直至组和排序操作；直至 di = 1，即所有记录
14、放进一个组中排序为止。即所有记录放进一个组中排序为止。 其中其中 d di i 称为称为增量增量增量增量。 例：例： 49 38 65 97 76 13 27 49 55 04 第一趟希尔排序第一趟希尔排序 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76第三趟希尔排序第三趟希尔排序 第一趟分组，设第一趟分组，设 d1 = 5 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 第二趟分组，设第二趟分组，设 d2 = 3 04 13 27 38 49 49
15、55 65 76 97第12页例例:待待排排序序列列为为 34，81，72，42，10，28，52，77，33，13，109，4，42，89。增量增量增量增量di分别取分别取5、3、1，则排序过程如下：，则排序过程如下：d0=534 81 72 42 10 28 52 77 33 13 109 4 42 89 子序列分别为子序列分别为34，28，109，81，52，4，72，77，42，42，33，89，10，13。 第13页第一趟排序结果：第一趟排序结果：28 4 42 33 10 34 52 72 42 13 109 81 77 89 第二趟排序结果：第二趟排序结果：13 4 34 28
16、13 42 33 72 42 52 89 81 77 109 此此时时，序序列列基基本本“有有序序”，对对其其进进行行直直接接插插入入排排序，得到最终结果：序，得到最终结果： 4 10 13 28 33 34 42 42 52 72 77 81 89 109第14页希尔排序特点希尔排序特点： 分组不是简单的分组不是简单的“逐段分割逐段分割”，而是将相隔某个增量的记录组成，而是将相隔某个增量的记录组成 一个子序列。一个子序列。 增量序列取法增量序列取法 希尔最早提出的选法是希尔最早提出的选法是 d1 = n/2 ，di +1 = di /2 。 克努特克努特 (Knuth) 提出的选法是提出的选
17、法是 di +1 = (di-1) /3 。 还有其他不同的取法。还有其他不同的取法。 如何选择增量序列以产生最好的排序效果，至今仍没有从数学如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。上得到解决。最后一个增量值必须为最后一个增量值必须为 1。 希尔排序可提高排序速度希尔排序可提高排序速度 1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。记录跳跃式前移，在进行最后一趟排序时，已基本有序。 2)、分组后、分组后 n 值减小，值减小，n2 更小，而更小，而 T(n)=O(n2)，所以所以 T(n) 从从 总体上看是减小了。总体上看是减小了。 第15页排序的基本概念1
18、交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第16页 3、重复直到重复直到 “在一趟排序在一趟排序在一趟排序在一趟排序 过程中没有进行过交换记录的操过程中没有进行过交换记录的操过程中没有进行过交换记录的操过程中没有进行过交换记录的操 作作作作” 或或“仅第一二个交换过仅第一二个交换过仅第一二个交换过仅第一二个交换过” 为止。为止。 冒泡排序算法冒泡排序算法冒泡排序算法冒泡排序算法( (改进改进改进改进) ) 交换排序交换排序 冒泡排序冒泡排序 v 排序过程排序过程 1、比较第一个记录与第二个、比较第一个记录与第二个 记录，若记录，若关键字关键字为逆序为逆序则交
19、换；然则交换；然 后比较第二个记录与第三个记录；后比较第二个记录与第三个记录； 依次类推，直至第依次类推，直至第 n -1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第一趟冒泡第一趟冒泡第一趟冒泡第一趟冒泡 排序排序排序排序，结果关键字最大的记录被安，结果关键字最大的记录被安 置在最后一个记录上。置在最后一个记录上。 2、对前对前 n-1 个记录进行第二个记录进行第二 趟冒泡排序，结果使关键字次大的趟冒泡排序，结果使关键字次大的 记录被安置在第记录被安置在第 n-1 个记录位置。个记录位置。 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一
20、趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 9797 38 49 65 76 13 27 49 979738 49 65 13 27 49 76 76 第第 二二 趟趟 排排 序序 38 49 13 27 49 65 65 第第 三三 趟趟 排排 序序 38 13 27 49 4949 第第 四四 趟趟 排排 序序 13 27 3849 49 第第 五五 趟趟 排排 序序 13 13 27 27 38 38 第第 六六 趟趟 排排 序序 for ( j = 1; j n n ; j + +) if ( r j +1 r j ) r j
21、r j + 1 ; for ( j = 1; j n n -1 -1; j + +) if ( r j +1 1; i - - ) i i ; while ( i 1) / while i = n ; i = k ; Void BubbleSort(SqList &L) 初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 k = j ; /交换的位置交换的位置 k = 1 ; 一般情况下每经过一般情况下每经过 一趟一趟“起泡起泡”，“ i 减减 1”， 但并不是每趟都如此。但并不是每趟都如此。 例：例： 5 2 3 1 9 7 8 2 3 1 5 7 8 9 2 1
22、3 5 7 8 9i = 6 i = 2 1 2 3 5 7 8 9i = 1 第17页v 算法评价算法评价 时间复杂度：时间复杂度： 最好情况（正序）最好情况（正序） 比较次数：比较次数：n -1 移动次数：移动次数：0 T(n) = O(n) 最坏情况（逆序）最坏情况（逆序） 比较次数：比较次数： 移动次数：移动次数： T T( (n n) = ) = O O( (n n2 2) ) 空间复杂度：空间复杂度：S(n) = O(1) 稳定性：稳定排序稳定性：稳定排序 第18页快速排序快速排序 设数组设数组A A中存放了中存放了n n个数据元素个数据元素,low,low为数组的为数组的低端下标
23、低端下标,high,high为数组的高端下标为数组的高端下标, ,从数组从数组A A中任中任意取一个元素意取一个元素( (一般是取一般是取A lowA low ) ) 作为中间元作为中间元素素, ,调整数组调整数组A A中各元素的位置。中各元素的位置。使得使得: :关键字比中间元素小的数据元素排在中间关键字比中间元素小的数据元素排在中间元素前面关键字比中间元素大的数据元素排在中元素前面关键字比中间元素大的数据元素排在中间元素后面间元素后面. .这样这样以中间元素为轴以中间元素为轴, ,将数组将数组A A中的中的元素划分成两个子数组元素划分成两个子数组, ,然后再对这两个子数组然后再对这两个子数
24、组分别进行快速排序分别进行快速排序第19页例例例例: :一趟快速排序过程示例一趟快速排序过程示例一趟快速排序过程示例一趟快速排序过程示例 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 28 39 76 98 69 4 51 58 28 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 28 39 76 98 69 4 51 58 28 low high 从从high向向前前搜搜索索小小于于r0.key的的记记录录(28)，将将其其赋赋值值给给low指指向的位置向的位置 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43
25、28 28 39 76 98 69 4 51 58 low high从从low向向后后搜搜索索大大于于r0.key的的记记录录(76) ，将将其其赋赋值值给给high指指向的位置向的位置 第20页r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r1043 28 28 39 98 69 4 51 58 76 low high 从从high向向前前搜搜索索小小于于r0.key的的记记录录(4)，将将其其赋赋值值给给low指向的位置指向的位置 43 28 28 39 4 98 69 51 58 76 low high 从从low向向后后搜搜索索大大于于r0.key的的记记录录(98)，将
26、将其其赋赋值值给给high指向的位置指向的位置第21页从从high向前搜索小于向前搜索小于r0.key的记录的记录 43 28 28 39 4 69 98 51 58 76 low high 43 28 28 39 4 69 98 51 58 76 low highhigh=low， 划划 分分 结结 束束 ， 将将 r0.key的的 值值 赋赋 值值 给给low(high)指向的位置指向的位置 28 28 39 4 43 69 98 51 58 76 大于等于大于等于43小于等于小于等于43第22页void QSort (SqList &L, int low, int high ) / 对顺
27、序表对顺序表 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if (low high) / 长度大于长度大于1 / QSortpivotlocpivotloc = Partition(L, low, high) ; = Partition(L, low, high) ; / / 对对对对 L.rlow.high L.rlow.high 进行一次划分进行一次划分进行一次划分进行一次划分 QSort(L, low, pivotloc-1) ; / 对低子序列递归排序，对低子序列递归排序，pivotloc 是是枢轴位置枢轴位置 QSort(L, pivotloc+1,
28、high); / 对高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时时，待排序记录序列的上、，待排序记录序列的上、 下界分别为下界分别为 1 和和 L.length。 void QuickSort( SqList & L) / 对顺序表进行快速排序对顺序表进行快速排序 QSort(L, 1, L.length); / QuickSort 第23页快速排序的时间分析快速排序的时间分析 假设一次划分所得枢轴位置假设一次划分所得枢轴位置 i=k，则对则对 n 个记录进行快排所个记录进行快排所 需时间：需时间：其中其中 Tpass(n) 为对为对 n 个记录进行一次划分
29、所需时间。个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k 取取 1 至至 n 中中 任一值的可能性相同。任一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k) 由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为：设设 Tavg(1)b，则可得结果：则可得结果： 结论：结论：结论：结论：快速排序的时间复杂度为快速排序的时间复杂度为 O(n log n)。 一次划分所需时间和表长成正比一次划分所需时间和表长成正比 第24页 若待排记录的初始状态为按关键字有序时，快速排序将蜕若待排
30、记录的初始状态为按关键字有序时，快速排序将蜕 化为起泡排序，其时间复杂度为化为起泡排序，其时间复杂度为 O(n2)。 所以快速排序适用于所以快速排序适用于 原始记录排列杂乱无章的情况。原始记录排列杂乱无章的情况。 快速排序是快速排序是平均速度最大平均速度最大的一种排序方法。的一种排序方法。 快速排序是一种快速排序是一种不稳定不稳定不稳定不稳定的排序，在递归调用时需要占据的排序，在递归调用时需要占据 一定的存储空间用来保存每一层递归调用时的必要信息。一定的存储空间用来保存每一层递归调用时的必要信息。 第25页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结
31、3 6第26页选择排序选择排序 直接选择排序直接选择排序 是以降低数据元素的移动次数为排序思路。是以降低数据元素的移动次数为排序思路。 排序过程：排序过程： 首先通过首先通过 n 1 次关键字比较，从次关键字比较，从 n 个记录中找出个记录中找出关键字最小关键字最小 的记录，将它与第一个记录交换。的记录，将它与第一个记录交换。 再通过再通过 n 2 次比较，从剩余的次比较，从剩余的 n 1 个记录中找出关键字次小个记录中找出关键字次小 的记录，将它与第二个记录交换。的记录，将它与第二个记录交换。 重复上述操作，共进行重复上述操作，共进行 n 1 趟排序后，排序结束。趟排序后，排序结束。 第27
32、页假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列 R1.i-1 无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n第28页例例:待排序列待排序列 35 28 45 55 19 68初始状态初始状态 35 28 45 55 19 68i=1 19 28 45 55 35 68 元素元素19和和35交换交换i=2 19 28 45 55 35 68 元素元素35和和45交换交换i=3 19 28 35 55 45 68 元素元素45和和
33、55交换交换i=4 18 24 35 45 55 68i=5 18 24 35 45 55 68i=6 18 24 35 45 55 68第29页j+ if (L.rj.key L.rk.key) k = j; j = i+1; for (i = 1; i L.length; + i) 例：例： 初始：初始： 49 38 65 97 76 13 27 jjjjjjki =1 13 49 一趟：一趟： 13 38 65 97 76 49 27 i =2 二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38
34、49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 排序结束：六趟：排序结束：六趟： 13 27 38 49 65 76 97 kk = i; kfor ( j = i+1; j = n; j+) if (L.rj.key 0; - - i ) HeapAdjust (H.r, i, H.length); / 建大顶堆建大顶堆 for ( i = H.length; i 1; - - i ) H.r1H.ri; / 将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列 / H.r1.i中最后一个记录相互
35、交换中最后一个记录相互交换 HeapAdjust (H.r, 1, i -1); / 对对 H.r1 进行筛选进行筛选 定义堆类型为：定义堆类型为： typedef SqList HeapType; / 堆用顺序表表示堆用顺序表表示 第41页堆排序的时间复杂度和空间复杂度：堆排序的时间复杂度和空间复杂度： 1. 对深度为对深度为 k 的堆，的堆，“筛选筛选”所需进行的关键字比较的次数至所需进行的关键字比较的次数至多多 为为 2(k-1)；3. 调整调整“堆顶堆顶” n-1 次，总共进行的关键字比较的次数不超过次，总共进行的关键字比较的次数不超过 2 ( log2(n-1) + log2(n-2
36、) + +log22) 2n( log2n ) 因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序与简单选择排序 O(n2) 相比时间效率提高了很多。相比时间效率提高了很多。 2. 对对 n 个关键字，建成深度为个关键字，建成深度为 h(= log2n +1) 的堆，的堆，所需所需进行的进行的 关键字比较的次数至多关键字比较的次数至多 4n； 空间复杂度：空间复杂度：S(n) = O(1) 堆排序是一种堆排序是一种速度快速度快速度快速度快且且省空间省空间省空间省空间的排序方法。的排序方法。 不稳定。不稳定。不稳定。不稳定。 第42页排序的基本概念1交换类排序
37、3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第43页归并排序归并排序 归并：归并：将两个或两个以上的有序表组合成一个新的有序表。将两个或两个以上的有序表组合成一个新的有序表。 在内部排序中，通常采用的是在内部排序中，通常采用的是 2-2-路归并排序路归并排序路归并排序路归并排序。即：将两个。即：将两个 位置相邻的记录有序子序列归并为一个记录有序的序列。位置相邻的记录有序子序列归并为一个记录有序的序列。 初始关键字：初始关键字： 49 38 65 97 76 13 27 一趟归并后：一趟归并后： 38 49 65 97 13 76 27 二趟归并后：二趟归并后： 38 4
38、9 65 97 13 27 76 三趟归并后：三趟归并后： 13 27 38 49 65 76 97 看成是看成是 n 个有序的子个有序的子 序列（长度为序列（长度为 1），）， 然后两两归并。然后两两归并。 得到得到 n/2 个长度为个长度为 2 或或 1 的有序子序列。的有序子序列。 空间复杂度为：空间复杂度为：O(n)。 时间复杂度为：时间复杂度为：O(nlog2n)。 稳定。稳定。 每趟归并的时间复每趟归并的时间复杂度为杂度为O(n)，共需进，共需进行行 log2n 趟。趟。第44页一、时间性能一、时间性能 时间复杂度为时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序快速排序
39、、堆排序和归并排序，其中以其中以 快速排序为最好。快速排序为最好。 时间复杂度为时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序，直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好，特别是对那些对关其中以直接插入为最好，特别是对那些对关其中以直接插入为最好，特别是对那些对关其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。 时间复杂度为时间复杂度为 O(n)：基数排序。基数排序。 1. 按平均时间性能来分，有三类排序方法：按平均时间性能来分，有三类排序方
40、法： 2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中简单选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而改变。关键字的分布而改变。各种排序方法的综合比较各种排序方法的综合比较 第45页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第46页二、空间性能二、空间性能 指的是排序过程中所需的辅助
41、空间大小。指的是排序过程中所需的辅助空间大小。 1.所有的简单排序方法所有的简单排序方法(包括：直接插入、冒泡和简单选择包括：直接插入、冒泡和简单选择) 和和 2. 堆排序的空间复杂度为堆排序的空间复杂度为 O(1)； 2.快速排序为快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助为递归程序执行过程中，栈所需的辅助 3. 空间；空间；3. 归并排序所需辅助空间最多，其空间复杂度为归并排序所需辅助空间最多，其空间复杂度为 O(n)； 4. 链式基数排序需附设队列首尾指针，则空间复杂度为链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。 三、排序方法的稳定性能三、排序方法的稳定性能 1. 当对多关键字的记录序列进行当对多关键字的记录序列进行LSD方法排序时，必须采用稳方法排序时，必须采用稳 定的排序方法。定的排序方法。2. 对于不稳定的排序方法，只要能举出一个实例说明即可。对于不稳定的排序方法，只要能举出一个实例说明即可。 3. 快速排序、堆排序和希尔排序是不稳定的排序方法快速排序、堆排序和希尔排序是不稳定的排序方法。
