[其它]ch10-内部排序.ppt

《[其它]ch10-内部排序.ppt》由会员分享，可在线阅读，更多相关《[其它]ch10-内部排序.ppt（59页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第10章章 内部排序内部排序10.1 10.1 排序简介排序简介10.2 10.2 插入排序插入排序10.3 10.3 快速排序快速排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序10.7 10.7 各种排序方法的比较各种排序方法的比较1本章知识点和要求本章知识点和要求各种排序方法的特点并能灵活应用（掌握）各种排序方法的特点并能灵活应用（掌握）各种方法的排序过程（掌握）各种方法的排序过程（掌握）各种排序方法的时间复杂度分析（掌握）各种排序方法的时间复杂度分析（掌握）210.1 排序简介排序简介 排序排序(sorting)(sor

2、ting)又称又称分类分类，意指把一批杂乱，意指把一批杂乱无章的数据序列重新排列成有序序列。无章的数据序列重新排列成有序序列。排序是程序设计中一种重要运算。在很多领排序是程序设计中一种重要运算。在很多领域中有广泛的应用。譬如，在查找时，若文件的域中有广泛的应用。譬如，在查找时，若文件的记录按关键字预先排好顺序，可以采用记录按关键字预先排好顺序，可以采用折半查找折半查找方法提高查找效率。折半查找的平均查找长度数方法提高查找效率。折半查找的平均查找长度数量级为量级为O(lognO(logn)，而顺序查找的平均查找长度数，而顺序查找的平均查找长度数量级为量级为O(nO(n)。又如，建立二叉排序树的过

3、程本身。又如，建立二叉排序树的过程本身就是一个排序过程。日常生活中的各类竞赛活动，就是一个排序过程。日常生活中的各类竞赛活动，如如歌唱大奖赛歌唱大奖赛等，还有各种等，还有各种升学考试录取升学考试录取工作均工作均离不开排序。离不开排序。310.1 排序简介排序简介关键字关键字 是数据元素中的某个数据项。如果某个数是数据元素中的某个数据项。如果某个数据项可以据项可以唯一地唯一地确定一个数据元素，就将其确定一个数据元素，就将其称称为主关键字为主关键字；否则，称为次关键字。；否则，称为次关键字。排序排序 将数据元素的任意序列将数据元素的任意序列,重新重新调整为调整为一个一个按按关键字排列有序关键字排列

4、有序的序列的序列.如如:有数据元素序列有数据元素序列(r1,r2,r3,r4,r5,r6,r7)其其对应关键字值为对应关键字值为:(5,4,8,6,9,1,21);按关键字按关键字非递非递减排列减排列得新的数据元数排列得新的数据元数排列(r6,r2,r1,r4,r3,r5,r7)的操作的操作.410.1 排序简介排序简介 一般情况下一般情况下:假设含假设含n n个记录的序列为个记录的序列为 R R1 1,R,R2 2,，R Rn n 其相应的关键字序列为其相应的关键字序列为 K K1 1,K,K2 2,，K Kn n 这些关键字相互之间可以进行比较，即在它们之间这些关键字相互之间可以进行比较，

5、即在它们之间存在着这样一个关系存在着这样一个关系 K Kp1p1KKp2p2K Kpnpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 R Rp1p1,R,Rp2p2,，R Rpnpn 的操作称作的操作称作排序。排序。5n 排序算法的稳定性排序算法的稳定性 如果在待排序的记录序列中有多个数据元素的如果在待排序的记录序列中有多个数据元素的关键字关键字值相同值相同，经过，经过排序后排序后，这些数据元素的，这些数据元素的相对次序保持不变相对次序保持不变，则称这种排序算法是则称这种排序算法是稳定的稳定的，否则称之为不稳定的。，否则称之为不稳定的。n 内部排序与外部排序内部排

6、序与外部排序 根据在排序过程中待排序的所有数据元素是否全部被根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两放置在内存中，可将排序方法分为内部排序和外部排序两大类。大类。内部排序内部排序是指在排序的整个过程中，待排序的所有数据元是指在排序的整个过程中，待排序的所有数据元素全部被放置在素全部被放置在内存中内存中；外部排序外部排序是指由于待排序的数据元素个数太多，不能同时是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放置在部分数据元素放置在外设

7、外设上，整个排序过程需要在内外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。之间多次交换数据才能得到排序的结果。6排序的基本方法排序的基本方法 内部排序主要有内部排序主要有5 5种方法：种方法：插入、交换、选择、归并和基数。插入、交换、选择、归并和基数。一趟一趟:在排序过程中，基本动作执行一次。在排序过程中，基本动作执行一次。排序算法的效率排序算法的效率评价排序算法的效率主要有两点：评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，一是在数据量规模一定的条件下，算法执行所消耗的平均算法执行所消耗的平均时间时间，对于排序操作，时间主要消耗在，对于排序操作，时间主要消

8、耗在关键字之间的比较关键字之间的比较和数据元素的移动和数据元素的移动上，因此我们可以认为高效率的排序算上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；次数；二是二是执行算法所需要的辅助存储空间执行算法所需要的辅助存储空间，辅助存储空间是指，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的用的存储空间之外，执行算法所需要的其他存储空间其他存储空间，理，理想的空间效率是算法执行期间所需要的辅助空间与待排序想

9、的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。的数据量无关。710.2 插插 入入 排排 序序 插入排序的思路 不断地将待排序的数值插入到有序段不断地将待排序的数值插入到有序段(序列序列)中中，使有序段使有序段(序列序列)逐渐扩大，直至所有数值都进逐渐扩大，直至所有数值都进入有序段中位置。入有序段中位置。直接插入排序 折半插入排序 希尔排序8直接插入排序1.1.首先将待排序记录序列中的首先将待排序记录序列中的第一个记录作为一个有第一个记录作为一个有序段序段;2.2.将记录序列中的第二个记录插入到上述有序段中形将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段成

10、由两个记录组成的有序段;3.3.再将记录序列中的第三个记录插入到这个有序段中，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段形成由三个记录组成的有序段;4.4.依此类推，每一趟都是将一个记录插入到前面的依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第有序段中，假设当前欲处理第i i个记录，则应该将这个记录，则应该将这个记录插入到由前个记录插入到由前i-1i-1个记录组成的有序段中，从而个记录组成的有序段中，从而形成一个由形成一个由i i个记录组成的按关键字值排列的有序序个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。列，直到所有

11、记录都插入到有序段中。5.5.一共需要经过一共需要经过n-1n-1趟趟就可以将初始序列的就可以将初始序列的n n个记录重个记录重新排列成按关键字值大小排列的有序序列新排列成按关键字值大小排列的有序序列。9例例49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27 ()i=7 (13 38 49 65 76 97)2727jjjjjj

12、977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：0 1 2 3 4 5 6 7 10算法评价算法评价时间复杂度时间复杂度若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列(正序正序)Y记录移动次数：记录移动次数：0 0 1 2 3 4 5 6 7 13 27 38 49 65 76 97Y关键字比较次数：关键字比较次数：11Y关键字比较次数：关键字比较次数：Y记录移动次数：记录移动次数：0 1 2 3 4 5 6 7 97 76 65 49 38 27 13n 若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列(逆序逆序)1

13、2若待排序记录是若待排序记录是随机的随机的，取平均值，取平均值Y关键字比较次数：关键字比较次数：Y记录移动次数：记录移动次数：T(n)=O(n)空间复杂度空间复杂度：S(n)=O(1)13 折半插入排序折半插入排序思想：用思想：用折半查找方法确定插入位置折半查找方法确定插入位置的排序叫的排序叫例例i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85)20.i=8 20 (6 13 30 39 42 70 85)20sjmi=8 20 (6 13 30 39 42 70 85)20s

14、jmi=8 20 (6 13 30 39 42 70 85)20sjmi=8 20 (6 13 30 39 42 70 85)20sji=8 20 (6 13 20 30 39 42 70 85)14 从上述过程可以看出从上述过程可以看出:折半插入排序仅折半插入排序仅减少了减少了关关键字之间的键字之间的比较次数比较次数,而记录的移动次数不变而记录的移动次数不变.算法评价算法评价时间复杂度：时间复杂度：T(n)=O(n)空间复杂度：空间复杂度：S(n)=O(1)15 希尔排序希尔排序(缩小增量法缩小增量法 ShellShells s Sort)Sort)排序过程排序过程：先取一个正整数：先取一个

15、正整数d1nd1n，把所有把所有相相隔隔d1d1的记录放一组，的记录放一组，组内组内进行进行直接插入排序直接插入排序；然后取然后取d2d1d2r2.key，则交换；然后比较则交换；然后比较第二个记录与第三个记录；依次类推，直至第第二个记录与第三个记录；依次类推，直至第n-1个个记录和第记录和第n个记录比较为止个记录比较为止第一趟冒泡排序第一趟冒泡排序，结，结果关键字最大的记录被安置在最后一个记录上果关键字最大的记录被安置在最后一个记录上对前对前n-1个记录进行第二趟冒泡排序，结果使关键字个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第次大的记录被安置在第n-1个记录位置个记录位置重复

16、上述过程，直到重复上述过程，直到“在一趟排序过程中没有进行过在一趟排序过程中没有进行过交换记录的操作交换记录的操作”为止为止22例例49 38 65 97 76 13 27 30 初初始始关关键键字字 38 49 65 76 13 27 30 97 第第一一趟趟38 49 65 13 27 30 76 第第二二趟趟38 49 13 27 30 65 第第三三趟趟38 13 27 30 49 第第四四趟趟13 27 30 38 第第五五趟趟384976971397279730971376767627301365276530651313494930492738273830381 2 3 4 5 6

17、 7 823算法描述算法描述算法评价算法评价时间复杂度时间复杂度最好情况（正序）最好情况（正序）Y比较次数：比较次数：n-1Y移动次数：移动次数：0最坏情况（逆序）最坏情况（逆序）Y比较次数：比较次数：Y移动次数：移动次数：空间复杂度：空间复杂度：S(n)=O(1)T(n)=O(n)24快速排序快速排序快速排序由霍尔快速排序由霍尔(Hoare)提出，它是一种对冒泡提出，它是一种对冒泡排序的改进。由于其排序速度快，因此称快速排序的改进。由于其排序速度快，因此称快速排序排序(quick sort)。基本思想：通过基本思想：通过一趟一趟排序，将排序，将待排序记录待排序记录分割分割成独立的成独立的两部

18、分两部分，其中一部分记录的关键字均，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序部分记录进行排序，以达到整个序列有序25v排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key1.初始时令i=s,j=t2.首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换3.再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换4.重复上述两步，直至i=j为止5.再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止26例例初始关键字：

19、初始关键字：49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：分别进行快速排序：(13)27 (38)49 (50 65)76 (97)快速排序结束：快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij27作作 业业1.习题册习题册 第第9章习题章习题10题题 2.有一随机数有一随机数25,84,21,46,13,27,68,35,20采用冒泡采用冒泡排序和快速排序方法对它们排序，写出每趟排序的过排序和快速排序方法对它们排序

20、，写出每趟排序的过程程习题习题10.有一随机数有一随机数25,84,21,46,13,27,68,35,20,现现采用某种方法对它们进行排序采用某种方法对它们进行排序,其每趟排序结果如下其每趟排序结果如下,则该排序方法是什么则该排序方法是什么?初初 始始:25,84,21,46,13,27,68,35,20 第一趟第一趟:20,13,21,25,46,27,68,35,84第二趟第二趟:13,20,21,25,35,27,46,68,84 第三趟第三趟:13,20,21,25,27,35,46,68,84该排序方法为快速排序。该排序方法为快速排序。2810.4 选择排序选择排序10.4.1 简

21、单选择排序简单选择排序排序过程排序过程首先通过首先通过n-1次次关键字比较，从关键字比较，从n个记个记录中找出关键字录中找出关键字最小最小的记录，将它与的记录，将它与第一个记录交换第一个记录交换再通过再通过n-2次次比较，从剩余的比较，从剩余的n-1个记个记录中找出录中找出关键字次小关键字次小的记录，将它与的记录，将它与第二个记录交换第二个记录交换重复上述操作，共进行重复上述操作，共进行n-1趟趟排序后，排序后，排序结束排序结束29例例初始：初始：49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟：13 38 65 97 76 49 27 i=2kkjjjjj

22、2738二趟：二趟：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 9730算法评价算法评价时间复杂度时间复杂度记录记录移动次数移动次数Y最好情况：最好情况：0Y最坏情况：最坏情况：3(n-1)比较次数比较次数：空间复杂度空间复杂度：S(n)=O(1)T(n)=O(n)3110.4.3 堆排序堆排序堆的定义：堆的定义：n个元素的序列

23、个元素的序列(k1,k2,kn)，当当且仅当满足下列关系时，称之为堆且仅当满足下列关系时，称之为堆或或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+1例例 （96，83，27，38，11，9）例例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中元素（完全二叉树的根）必为序列中n个元素的最小值或最大值个元素的最小值或最大值32n堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一

24、个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？使之成为一个新的堆？n第二个问题解决方法第二个问题解决方法筛选筛选 方法：方法：输出堆顶元素输出堆顶元素之后，以堆中之后，以堆中最后一最后一个元素个元素替代之；然后将替代之；然后将根结点值与左、右子树根结点值与左、右子树的根结点值的根结点值进行比较，并与其中进行比较，并与其中小者进行交换小者进行交换；重复上述操作，重复上述操作，直至叶子直至叶子结点，将得到新的堆，结点，将得到新的堆，称这个从堆顶至叶子的调整过程为称这个从堆顶至叶子的调整过程为“筛选筛选”n堆排序堆排序：将无序序

25、列：将无序序列建成一个堆建成一个堆，得到关键字最小，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩（或最大）的记录；输出堆顶的最小（大）值后，使剩余的余的n-1n-1个元素重个元素重又建成一个堆又建成一个堆，则可得到，则可得到n n个元素的次个元素的次小值；重复执行，得到一个有序序列，这个过程叫小值；重复执行，得到一个有序序列，这个过程叫 33例例13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 2

26、76549502738769713输出：输出：13 27 38344965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 65357665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：

27、输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 9736第一个问题解决方法第一个问题解决方法从无序序列的第从无序序列的第 n/2 个元素（即个元素（即此无序序列对应的完全二叉树的此无序序列对应的完全二叉树的最后一个非终端结点）起，至最后一个非终端结点）起，至第第一个一个元素止，进行元素止，进行反复筛选反复筛选37例例 含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133

28、827657650971327384965765097 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 505097136538132749491338276576509738算法评价算法评价时间复杂度：最坏情况下时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：空间复杂度：S(n)=O(1)39作作 业业习题册习题册 第第9章习题章习题12 12.判断下列序列是否是堆（可以是小根堆，也可以是判断下列序列是否是堆（可以是小根堆，也可以是大根堆，若不是堆，请将它们调整为堆）。大根堆，若不是堆，请将它们调整为堆）。(1)100，85，98，77，80，60，82

29、，40，20，10，66 (2)100，98，85，82，80，77，66，60，40，20，10 (3)100，85，40，77，80，60，66，98，82，10，20(4)10，20，40，60，66，77，80，82，85，98，10012.答：答：(1)是大根堆；是大根堆；(2)是大根堆；是大根堆；(3)不是堆，调不是堆，调成大根堆为：成大根堆为：(100,98,66,85,80，60,40,77,82,10,20)；(4)是小根堆；是小根堆；4010.5 归并排序归并排序归并归并将两个或两个以上的有序表组合成一将两个或两个以上的有序表组合成一个新的有序表，叫个新的有序表，叫2-路归

30、并排序路归并排序排序过程排序过程设初始序列含有设初始序列含有n个记录，则可看成个记录，则可看成n个个有有序的子序列，每个子序列序的子序列，每个子序列长度为长度为1两两合并两两合并，得到，得到 n/2 个长度为个长度为2或或1的有序的有序子序列子序列再两两合并再两两合并，如此重复，直至得到如此重复，直至得到一一个个长度为长度为n的的有序序列有序序列为止为止41例例初始关键字：初始关键字：49 38 65 97 76 13 27一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 4

31、9 65 76 9742算法评价算法评价时间复杂度：时间复杂度：T(n)=O(nlog2n)空间复杂度：空间复杂度：S(n)=O(n)438.5 基数排序基数排序多关键字多关键字排序排序定义：定义：例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（两个关键字：花色（）面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”44多关键字排序方法多关键字排序方法最高位优先法最高位优先法（MSD)：先对先对最高位最高位关键字关键字k1（如花色）如花色）排序排序，将序列分，将序列分成成若干子序列若干子序列，每个子序

32、列有相同的，每个子序列有相同的k1值；然后值；然后让每个子序列对次关键字让每个子序列对次关键字k2（如面值）如面值）排序排序，又分成若干更小，又分成若干更小的子序列；依次重复，直至就每个子的子序列；依次重复，直至就每个子序列序列对最低位关键字对最低位关键字kd排序；最后将排序；最后将所有子序列依次连接在一起所有子序列依次连接在一起成为一个成为一个有序序列有序序列45最低位优先法最低位优先法(LSD)：从从最低位最低位关键字关键字kd起进行排序，然后再对高一位的关键字起进行排序，然后再对高一位的关键字排序，排序，依次重复，依次重复，直至对最高位直至对最高位关键字关键字k1排序后，便成为一个有序序

33、列排序后，便成为一个有序序列MSD与与LSD不同特点不同特点按按MSD排序，必须将序列逐层分割成排序，必须将序列逐层分割成若若干子序列干子序列，然后对各子序列分别排序，然后对各子序列分别排序按按LSD排序，排序，不必分成子序列不必分成子序列，对每个关，对每个关键字都是整个序列参加排序；并且可不通键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集过关键字比较，而通过若干次分配与收集实现排序实现排序46链式基数排序链式基数排序基数排序基数排序：借助：借助“分配分配”和和“收集收集”对单逻辑关键字进行排序的一种方法对单逻辑关键字进行排序的一种方法链式基数排序链式基数排序：用：用

34、链表链表作存储结构的作存储结构的基数排序基数排序47链式基数排序步骤链式基数排序步骤设置设置10个队列，个队列，fi和和ei分别为第分别为第i个队列个队列的头指针和尾指针的头指针和尾指针第一趟分配对最低位关键字（个位）进行，第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个链队列中，每个队列记录的关键字的个位相同个位相同第一趟收集是改变所有非空队列的队尾记第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的录的指针域，令其指向下一个非空队列的队头记录，重新将队头记录，重新将1

35、0个队列链成一个链表个队列链成一个链表重复上述两步，进行第二趟、第三趟分配重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得和收集，分别对十位、百位进行，最后得到一个有序序列到一个有序序列48例例初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：49505008109930063269278083184589二

36、趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：50008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集：二趟收集：51算法描述算法描述算法评

37、价算法评价时间复杂度时间复杂度：分配分配：T(n)=O(n)收集收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：其中：n记录数记录数 d关键字数关键字数 rd关键字取值范围关键字取值范围 空间复杂度空间复杂度：S(n)=2rd个队列指针个队列指针52一一.时间性能时间性能1.当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时2.简单选择排序简单选择排序、堆排序堆排序和和归并排序归并排序的时间性能的时间性能不不随随记录序列中关键字的分布而改变记录序列中关键字的分布而改变。直接插入排序直接插入排序和和起泡排序起泡排序能达到能达到O(n)的时间复杂度的时间复杂度;快速排序快

38、速排序的时间性能的时间性能蜕化为蜕化为O(n2)10.7 各种排序方法的综合比较各种排序方法的综合比较53二、空间性能二、空间性能二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小指的是排序过程中所需的辅助空间大小1.所有的所有的简单排序方法简单排序方法(包括：直接插入、包括：直接插入、起泡和简单选择起泡和简单选择)和堆排序和堆排序的空间复杂度的空间复杂度为为O(1)；2.快速排序为快速排序为O(logn)，为递归程序执行过程中，栈所为递归程序执行过程中，栈所需的辅助空间需的辅助空间;10.7 各种排序方法的综合比较各种排序方法的综合比较3.归并排序归并排序所需辅助空间最多，其空间复杂

39、度为所需辅助空间最多，其空间复杂度为 O(n);4.链式基数排序链式基数排序需附设队列首尾指针，则空间复杂度需附设队列首尾指针，则空间复杂度为为 O(rd)。54三、排序方法的稳定性能三、排序方法的稳定性能三、排序方法的稳定性能三、排序方法的稳定性能 1.稳定的排序方法指的是，对于稳定的排序方法指的是，对于两个关键字相等的记录，两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。没有改变。排序之前排序之前:Ri(K)Rj(K)排序之后排序之后:Ri(K)Rj(K)10.7 各种排序方法的综合比较各种排序方法的综合比

40、较55例如：例如：排序前排序前(56,34,47,23,66,18,82,47)若排序后得到结果若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是稳定稳定的的;若排序后得到结果若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是不稳定不稳定的的;10.7 各种排序方法的综合比较各种排序方法的综合比较56 3.对于不稳定的排序方法，只要能举出一个实例说明对于不稳定的排序方法，只要能举出一个实例说明即可。即可。4.快速排序快速排序、堆排序堆排序和和希尔排序希尔排序是不稳定的排序方法是不稳定的排序方法。

41、例如例如:对对 4,3,4,2 进行快速排序，进行快速排序，得到得到 2,3,4,4 10.7 各种排序方法的综合比较各种排序方法的综合比较57四、关于四、关于四、关于四、关于“排序方法的时间复杂度的下限排序方法的时间复杂度的下限排序方法的时间复杂度的下限排序方法的时间复杂度的下限”本章讨论的各种排序方法，除基数排序外，其它方法本章讨论的各种排序方法，除基数排序外，其它方法都是基于都是基于“比较关键字比较关键字”进行排序的排序方法。进行排序的排序方法。可以证明，可以证明，这类排序法这类排序法可能达到的最快的时间复杂可能达到的最快的时间复杂度为度为O(nlogn)。(基数排序不是基于基数排序不是基于“比较关键字比较关键字”的排序方法，所以它不受这个限制的排序方法，所以它不受这个限制)10.7 各种排序方法的综合比较各种排序方法的综合比较5810.7 各种排序方法的综合比较59