数据结构-排序.优秀PPT.ppt

第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，其相应的关键字序列为其相应的关键字序列为 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 Kp5 Kp6 Kp7 Kp8 按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1,Rp2,Rpn 的操作称作的操作称作排序排序排序排序。Rp1,Rp2,Rp3,Rp4,Rp5,Rp6,Rp7,Rp8 第4页 若若 Ki 为记录为记录 Ri 的的主主主主关键字，则排序关键字，则排序结果惟一结果惟一结果惟一结果惟一。若若 Ki 为记录为记录 Ri 的的次次次次关键字，则排序关键字，则排序结果结果结果结果可以可以不惟一不惟一不惟一不惟一（因为（因为 会有相同的关键字）。会有相同的关键字）。例：例：设排序前的关键字序列为：设排序前的关键字序列为：52,49,80,36,14,58,3636,23 若排序后的关键字序列为：若排序后的关键字序列为：14,23,36,3636,49,52,58,80，则则排序方法是稳定的排序方法是稳定的排序方法是稳定的排序方法是稳定的。若排序后的关键字序列为：若排序后的关键字序列为：14,23,3636,36,49,52,58,80，则则排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的排序方法是不稳定的。第5页 内部排序和外部排序内部排序和外部排序 若整个排序过程不须要访问外存便能完成，则称此类排序问若整个排序过程不须要访问外存便能完成，则称此类排序问 题为内部排序；题为内部排序；反之，若参与排序的记录数量很大，整个序列的排序过程不反之，若参与排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序可能在内存中完成，则称此类排序问题为外部排序(本章不探讨本章不探讨)。内部排序的方法内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列的过程。内部排序的过程是一个逐步扩大记录的有序序列的过程。有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区经过一趟排序经过一趟排序 第6页排序方法分类：排序方法分类：1)、插入排序：、插入排序：直接插入排序、折半插入排序、希尔排序直接插入排序、折半插入排序、希尔排序 2)、交换排序：、交换排序：冒泡排序、快速排序冒泡排序、快速排序 3)、选择排序：、选择排序：简单选择排序、堆排序简单选择排序、堆排序 4)、归并排序：、归并排序：2-路归并排序路归并排序 5)、基数排序、基数排序 基于不同的基于不同的“扩大扩大”有序序列长度的方法，内部排序有序序列长度的方法，内部排序 方法大致可分下列几种类型：方法大致可分下列几种类型：依次将无序子序列中的一依次将无序子序列中的一 个记录个记录“插入插入插入插入”到有到有 序序列中，序序列中，从而增加记录从而增加记录 的有序子序列的的有序子序列的长度。长度。通过通过“交换交换交换交换”无序序列中的记录从而无序序列中的记录从而 得到其中得到其中关键字最小关键字最小或或最大最大的记录，并的记录，并 将它将它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。从记录的无序子序列中从记录的无序子序列中“选择选择选择选择”关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加记录的有序子序列的长度。加记录的有序子序列的长度。通过通过“归并归并归并归并”两个两个 或两个以上的记录有或两个以上的记录有 序子序列，逐步增加序子序列，逐步增加 记录有序序列的长度。记录有序序列的长度。基数排序是一种基于多基数排序是一种基于多 关键字排序的思想，将单关关键字排序的思想，将单关 键字按基数分成键字按基数分成“多关键字多关键字”进行排序的方法。进行排序的方法。第7页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第8页插入排序插入排序 一趟干脆插入排序的基本思想：一趟干脆插入排序的基本思想：有序序列有序序列 R1.i-1 Ri无序序列无序序列 Ri.n有序序列有序序列 R1.i无序序列无序序列 Ri+1.n实现实现“一趟插入排序一趟插入排序”可分可分三步三步进行：进行：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 3849657697132749494938659776132749 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 个记录起先，逐个进行插入，直至整个序列有序。个记录起先，逐个进行插入，直至整个序列有序。在在 R1.i-1中查找中查找 Ri 的插入位置的插入位置;对于在查找过程中找到的那些关键字对于在查找过程中找到的那些关键字 不小于不小于 Ri.key 的记录，在查找的同的记录，在查找的同 时实现记录向后移动；时实现记录向后移动；插入插入插入插入 R Ri 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.r0;/插入到正确位置插入到正确位置插入到正确位置插入到正确位置 第10页比较次数和移动次数均比较次数和移动次数均约约约约为：为：T(n)=O(n)算法评价算法评价 时间困难度：时间困难度：比较次数：比较次数：移动次数：移动次数：0 最好的状况：待排序记录按关键字从小到大排列（正序）最好的状况：待排序记录按关键字从小到大排列（正序）比较次数：比较次数：移动次数：移动次数：最坏的状况：待排序记录按关键字从大到小排列（逆序）最坏的状况：待排序记录按关键字从大到小排列（逆序）一般状况：待排序记录是随机的，取平均值。一般状况：待排序记录是随机的，取平均值。空间困难度：空间困难度：S(n)=O(1)干脆插入排序是稳定排序干脆插入排序是稳定排序 5 4 3 2 1 第11页其次趟希尔排序其次趟希尔排序 第三趟分组，设第三趟分组，设 d3=1 希尔排序（缩小增量排序）希尔排序（缩小增量排序）基本思想基本思想：对待排序列先作对待排序列先作“宏观宏观”调整，再作调整，再作“微观微观”调调整。整。排序过程：先取一个正整数排序过程：先取一个正整数 d1 n，把全部相隔，把全部相隔 d1 的记录放的记录放 在一组内，组内进行干脆插入排序；然后取在一组内，组内进行干脆插入排序；然后取 d2 d1，重复上述分，重复上述分 组和排序操作；直至组和排序操作；直至 di=1，即全部记录放进一个组中排序为止。，即全部记录放进一个组中排序为止。其中其中 di 称为增量。称为增量。例：例：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 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 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)提出的选法是提出的选法是 di+1=(di-1)/3。还有其他不同的取法。还有其他不同的取法。如何选择增量序列以产生最好的排序效果，至今仍没有从数学如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。上得到解决。最终一个增量值必需为最终一个增量值必需为 1。希尔排序可提高排序速度希尔排序可提高排序速度 1)、记录跳动式前移，在进行最终一趟排序时，已基本有序。、记录跳动式前移，在进行最终一趟排序时，已基本有序。2)、分组后、分组后 n 值减小，值减小，n2 更小，而更小，而 T(n)=O(n2)，所以，所以 T(n)从从 总体上看是减小了。总体上看是减小了。第15页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第16页 3、重复直到重复直到 “在一趟排序在一趟排序在一趟排序在一趟排序 过程中没有进行过交换记录的操过程中没有进行过交换记录的操过程中没有进行过交换记录的操过程中没有进行过交换记录的操 作作作作”或或“仅第一二个交换过仅第一二个交换过仅第一二个交换过仅第一二个交换过”为止。为止。冒泡排序算法冒泡排序算法冒泡排序算法冒泡排序算法(改进改进改进改进)交换排序交换排序 冒泡排序冒泡排序 v 排序过程排序过程 1、比较第一个记录与其次个、比较第一个记录与其次个 记录，若关键字为逆序则交换；然记录，若关键字为逆序则交换；然 后比较其次个记录与第三个记录；后比较其次个记录与第三个记录；依次类推，直至第依次类推，直至第 n-1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第一趟冒泡第一趟冒泡 排序，结果关键字最大的记录被安排序，结果关键字最大的记录被安 置在最终一个记录上。置在最终一个记录上。2、对前、对前 n-1 个记录进行其次个记录进行其次 趟冒泡排序，结果使关键字次大的趟冒泡排序，结果使关键字次大的 记录被安置在第记录被安置在第 n-1 个记录位置。个记录位置。初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 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 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 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中存放了中存放了n个数据元素个数据元素,low为数组的低端下标为数组的低端下标,high为数组的高端下标为数组的高端下标,从数组从数组A中随意取一个元素中随意取一个元素(一般是取一般是取A low)作为中间元素作为中间元素,调整数组调整数组A中各元素的位置。中各元素的位置。使得使得:关键字比中间元素小的数据元素排在中间元素前面关键字比关键字比中间元素小的数据元素排在中间元素前面关键字比中间元素大的数据元素排在中间元素后面中间元素大的数据元素排在中间元素后面.这样以中间元素为轴这样以中间元素为轴,将数组将数组A中的元素划分成两个子数组中的元素划分成两个子数组,然后再对这两个子数组分别然后再对这两个子数组分别进行快速排序进行快速排序第19页例例例例:一趟快速排序过程示例一趟快速排序过程示例一趟快速排序过程示例一趟快速排序过程示例 r0 r0 r1 r1 r2 r2 r3 r3 r4 r4 r5 r5 r6 r6 r7 r7 r8 r8 r9 r9 r10 r10 43 43 28 28 39 39 76 76 98 98 69 69 4 4 51 51 58 58 28 28 r0 r0 r1 r1 r2 r2 r3 r3 r4 r4 r5 r5 r6 r6 r7 r7 r8 r8 r9 r9 r10 r10 43 43 28 28 39 39 76 76 98 98 69 69 4 4 51 51 58 58 2828 low low highhigh 从从从从highhigh向向向向前前前前搜搜搜搜寻寻寻寻小小小小于于于于r0.keyr0.key的的的的记记记记录录录录(28)(28)，将将将将其其其其赋赋赋赋值值值值给给给给lowlow指向的位置指向的位置指向的位置指向的位置 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 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)，将将其其赋赋值值给给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)/对依次表对依次表 L 中的子序列中的子序列 L.rlow.high 进行快速排序进行快速排序 if(low high)/长度大于长度大于1 /QSortpivotloc=Partition(L,low,high);pivotloc=Partition(L,low,high);/对对对对 L.rlow.high L.rlow.high 进行一次划分进行一次划分进行一次划分进行一次划分 QSort(L,low,pivotloc-1);/对低子序列递归排序，对低子序列递归排序，pivotloc 是枢轴位置是枢轴位置 QSort(L,pivotloc+1,high);/对高子序列递归排序对高子序列递归排序 第一次调用函数第一次调用函数 Qsort 时，待排序记录序列的上、时，待排序记录序列的上、下界分别为下界分别为 1 和和 L.length。void QuickSort(SqList&L)/对依次表进行快速排序对依次表进行快速排序 QSort(L,1,L.length);/QuickSort 第23页快速排序的时间分析快速排序的时间分析 假设一次划分所得枢轴位置假设一次划分所得枢轴位置 i=k，则对，则对 n 个记录进行快排所个记录进行快排所 需时间：需时间：其中其中 Tpass(n)为对为对 n 个记录进行一次划分所需时间。个记录进行一次划分所需时间。若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k 取取 1 至至 n 中中 任一值的可能性相同。任一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)由此可得快速排序所需时间的平均值为：由此可得快速排序所需时间的平均值为：设设 Tavg(1)b，则可得结果：，则可得结果：结论：快速排序的时间困难度为结论：快速排序的时间困难度为结论：快速排序的时间困难度为结论：快速排序的时间困难度为 O(n log n)O(n log n)。一次划分所需时间和表长成正比一次划分所需时间和表长成正比 第24页 若待排记录的初始状态为按关键字有序时，快速排序将蜕若待排记录的初始状态为按关键字有序时，快速排序将蜕 化为起泡排序，其时间困难度为化为起泡排序，其时间困难度为 O(n2)。所以快速排序适用于所以快速排序适用于 原始记录排列杂乱无章的状况。原始记录排列杂乱无章的状况。快速排序是快速排序是平均速度最大平均速度最大的一种排序方法。的一种排序方法。快速排序是一种不稳定的排序，在递归调用时须要占据快速排序是一种不稳定的排序，在递归调用时须要占据 确定的存储空间用来保存每一层递归调用时的必要信息。确定的存储空间用来保存每一层递归调用时的必要信息。第25页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第26页选择排序选择排序 干脆选择排序干脆选择排序 是以降低数据元素的移动次数为排序思路。是以降低数据元素的移动次数为排序思路。排序过程：排序过程：首先通过首先通过 n 1 次关键字比较，从次关键字比较，从 n 个记录中找出关键字最小个记录中找出关键字最小 的记录，将它与第一个记录交换。的记录，将它与第一个记录交换。再通过再通过 n 2 次比较，从剩余的次比较，从剩余的 n 1 个记录中找出关键字次小个记录中找出关键字次小 的记录，将它与其次个记录交换。的记录，将它与其次个记录交换。重复上述操作，共进行重复上述操作，共进行 n 1 趟排序后，排序结束。趟排序后，排序结束。第27页假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列 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和和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 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中最终一个记录相互交换中最终一个记录相互交换 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)+log22)2n(log2n)因此，堆排序的时间困难度为因此，堆排序的时间困难度为 O(nlogn)，与简洁选择排序，与简洁选择排序 O(n2)相比时间效率提高了很多。相比时间效率提高了很多。2.对对 n 个关键字，建成深度为个关键字，建成深度为 h(=log2n+1)的堆，的堆，所需所需进行的进行的 关键字比较的次数至多关键字比较的次数至多 4n；空间困难度：空间困难度：S(n)=O(1)堆排序是一种堆排序是一种速度快速度快速度快速度快且且省空间省空间省空间省空间的排序方法。的排序方法。不稳定。不稳定。不稳定。不稳定。第42页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第43页归并排序归并排序 归并：归并：将两个或两个以上的有序表组合成一个新的有序表。将两个或两个以上的有序表组合成一个新的有序表。在内部排序中，通常接受的是在内部排序中，通常接受的是 2-路归并排序。即：将两个路归并排序。即：将两个 位置相邻的记录有序子序列归并为一个记录有序的序列。位置相邻的记录有序子序列归并为一个记录有序的序列。初始关键字：初始关键字：49 38 65 97 76 13 27 一趟归并后：一趟归并后：38 49 65 97 13 76 27 二趟归并后：二趟归并后：38 49 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)：快速排序、堆排序和归并排序，其中以：快速排序、堆排序和归并排序，其中以 快速排序为最好。快速排序为最好。时间困难度为时间困难度为 O(n2)：干脆插入排序、起泡排序和简洁选择排序，：干脆插入排序、起泡排序和简洁选择排序，其中以干脆插入为最好，特殊是对那些对关其中以干脆插入为最好，特殊是对那些对关 键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。时间困难度为时间困难度为 O(n)：基数排序。：基数排序。1.按平均时间性能来分，有三类排序方法：按平均时间性能来分，有三类排序方法：2.当待排序列按关键字依次有序时，干脆插入排序和起泡排序能当待排序列按关键字依次有序时，干脆插入排序和起泡排序能 达到达到 O(n)的时间困难度，快速排序的时间性能蜕化为的时间困难度，快速排序的时间性能蜕化为 O(n2)。3.简洁选择排序、堆排序和归并排序的时间性能不随记录序列中简洁选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而变更。关键字的分布而变更。各种排序方法的综合比较各种排序方法的综合比较 第45页排序的基本概念1交换类排序3 3选择类排序3 4插入类排序3 2目 录归并排序3 5小结3 6第46页二、空间性能二、空间性能 指的是排序过程中所需的协助空间大小。指的是排序过程中所需的协助空间大小。1.全部的简洁排序方法全部的简洁排序方法(包括：干脆插入、冒泡和简洁选择包括：干脆插入、冒泡和简洁选择)和和 2.堆排序的空间困难度为堆排序的空间困难度为 O(1)；2.快速排序为快速排序为 O(logn)，为递归程序执行过程中，栈所需的协助，为递归程序执行过程中，栈所需的协助 3.空间；空间；3.归并排序所需协助空间最多，其空间困难度为归并排序所需协助空间最多，其空间困难度为 O(n)；4.链式基数排序需附设队列首尾指针，则空间困难度为链式基数排序需附设队列首尾指针，则空间困难度为 O(rd)。三、排序方法的稳定性能三、排序方法的稳定性能 1.当对多关键字的记录序列进行当对多关键字的记录序列进行LSD方法排序时，必需接受稳方法排序时，必需接受稳 定的排序方法。定的排序方法。2.对于不稳定的排序方法，只要能举出一个实例说明即可。对于不稳定的排序方法，只要能举出一个实例说明即可。3.快速排序、堆排序和希尔排序是不稳定的排序方法快速排序、堆排序和希尔排序是不稳定的排序方法。