十章节内部排序.ppt

《十章节内部排序.ppt》由会员分享，可在线阅读，更多相关《十章节内部排序.ppt（149页珍藏版）》请在三一文库上搜索。

1、第十章 内部排序,本章内容,讨论和比较各种排序方法：插入排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。 在每类排序方法中，重点讨论性能先进的高效方法(如，交换排序类中的快速排序，选择排序类中的堆排序等)。,本章要点,理解各种排序方法的特点，并能加以灵活应用； 了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法； 掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能； 快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。,基本概念,排序 排序又称分类，是计算机中很重

2、要的操作，它是将一个数据元素（或记录）的任意序列排列成一个按关键字有序的序列。 定义 设有记录序列R1、R2Rn，其相应的关键字序列为K1、K2Kn； 若存在一种确定的关系：KxKy Kz，则将记录序列R1、R2Rn排成按该关键字有序的序列 Rx、Ry Rz的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。 排序过程中的两种基本操作 比较操作：比较两个关键字值的大小的操作。 移动操作：将记录从一个位置移动到另一个位置的操作。,基本概念（续）,排序方法 稳定的排序方法 若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj (1ijn)，即排序前Ri在Rj前，若在排序后 R

3、i仍在Rj前，则称排序是稳定的。 不稳定的排序方法 待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1i jn)，即排序前Ri在Rj前，若在排序后Rj却在Ri前，则称排序是不稳定稳定的。,基本概念（续）,排序的分类 内部排序 待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序 外部排序 待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。 待排序列的三种存储结构 顺序存储：存储在地址连续的一组存储单元中（以此为例）； 链式存储：存储在地址不连续的一组存储单元（链表）中； 地址存储：记录顺序存储，另设关键字和

4、记录地址排序。,7,r0 用作哨兵。共执行 5 遍操作。 每遍操作：先将元素复制内容放入r0，再将本元素与已排序的序列从尾开始进行比较。在已排序的序列中寻找自己的位置进行插入，或者寻找不到，一直进行到哨兵为止，意味着本元素最小，应该放在 r1 。 每进行一遍，排序的序列将增加一个元素。如果序列中有 n 个元素，那么最多进行n 遍即可。,e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。,0,1,2,36,24,10,6,12,3,4,5,10.1 插入排序,直接插入排序,8,直接插入排序,9

5、,直接插入排序,10,直接插入排序,11,直接插入排序,12,直接插入排序,13,直接插入排序,14,直接插入排序,15,直接插入排序,16,直接插入排序,17,直接插入排序,18,直接插入排序,19,直接插入排序,20,直接插入排序,21,直接插入排序,22,直接插入排序,23,直接插入排序,24,分析: 移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 1 = n-1 i=2 移动次数 0,n,逆序时：比较次数 i = (n+2)(n-1)/2 i=2 移动次数 (i+1) = (n+4)(n-1)/2 i=2,n,n,O(n2),直接插入排序,直接插入排序,一种简单的排序方法

6、将记录一个个插入到已排序好的有序表中，从而得到长度增加的新的有序表。,void InsertSort () for (i = 2; i = n; i+) r0 = ri; for (j = i - 1; r0 rj; j-) rj+1 = rj; rj+1 = r0; ,插入排序（续）,直接插入排序性能分析 比较次数 最好情况 n-1 最坏情况 (n+2)(n-1)/2 平均比较次数 (n+4)(n-1)/4 移动次数 最好情况 2(n-1) 最坏情况 (n+4)(n-1)/2 平均移动次数 (n+8)(n-1)/4 直接插入排序的时间复杂度为 O(n2)。但在待排序列有序的的情况下，直接插入

7、排序的时间复杂度下降为 O(n)。,插入排序（续）,折半插入排序 与直接插入排序不同之处在于查找插入位置时不是用顺序查找，而是用折半查找。 移动次数与直接插入排序相同，只是比较次数少了，因此其时间复杂度也为 O(n2)。 2-路插入排序 目的：减少排序过程中移动记录的次数； 代价：需要 n 个记录的辅助空间d 将 r1 赋值给d1，将d 看成循环的，其它记录均与 d1 比较，比较小则在 d1 前插入，反之则在 d1 后插入。 表插入排序 附设指针域，改变指针的值，不移动记录而得到排序结果,28,Status InsertSort() for ( i = 2; i = high + 1; j-)

8、 rj+1 = rj; rhigh+1 = r0; ,方法：在已排序的序列中查找下一元素的插入位置，将该元素插入进去，形成更长的排序序列。如： 12 的插入位置为下标 3。 减少了比较次数，未降低时间复杂性。,折半插入排序,29,折半插入排序,30,折半插入排序,插入排序（续）,希尔排序“缩小增量排序” 用一定的增量间隔将待排序列分组，每组都采用简单插入排序 排序完一遍后，缩小增量间隔，再对新的分组采用简单插入排序；反复此过程，直至增量间隔为 1 ，即整个待排序列为一组时，执行一遍简单插入排序后结束。,希尔排序,希尔排序的时间复杂度与增量序列有关，分析起来很复杂，有人认为为 O(n1.5)，也

9、有人认为为 O(n1.3)； 如何选择最佳d序列，目前尚未解决； dltak = 2t-k+1-1 0ktlog2(n-1) dltak = 2t-k+1 0ktlog2(n-1) dltak=(3t-k-1)/2 0ktlog3(2n+1) 1: 8191 4095 2047 1023 511 255 127 63 31 15 7 5 3 1 2: 8193 2049 1025 513 257 129 65 33 17 9 5 3 2 1 3: 3280 1093 364 121 40 13 4 1 最后一个增量值必须为1 避免增量序列中的值（尤其是相邻的值）有公因子 希尔排序为不稳定排序

10、希尔排序简单，仅需要一个单元额外的辅助空间，在随机情况和数据有序情况下，对效率几乎没有影响。对于小数据量（几百/几千个数据元素）排序性能稳定并且效率不比其它方法差,希尔排序算法,数据存放于r1rn void shell_sort () for (k = 0; k 0 ,希尔排序C 语言实现,/* 31,15,7,3,1 */ void shell_sort(void) int t, k, i, j, dk, rc; t = 0; while (1 0 ,10.2 交换排序,起泡排序（冒泡排序） 将相邻两记录一一比较，将关键字较小的记录交换在前面，反复此过程，直到待排序列有序为止。 是一种稳定的

11、排序，时间复杂度为O(n2)。,bubble_sort() /* 数据存于r1rN */ int i, j, flag; for (i = n; i 1; i-) flag = 0; for (j = 1; j i; j+) if (rj rj+1) swap(rj, rj+1); flag = 1; if (flag) break; ,起泡排序,原理: 序列中有n个元素，进行n-1趟(条件满足时可以提前结束) 第1趟，针对r1n元素进行。 第2趟，针对r1(n-1)元素进行。 第n-1趟，针对 r12元素进行。 每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不

12、正确，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换 时间复杂性: 正序时 O(n)，逆序时 O(n2)。平均时间复杂性 O(n2),起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,

13、起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、

14、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、

15、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。

16、,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27

17、、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49

18、、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序

19、。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,起泡排序,e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。,80,交换排序（续）,快速排序 是对起泡排序的改进； 将待排序列第

20、一个元素(枢轴元素)放置到序列中的某个位置，使其前面的所有元素都小于它，后面的所有元素都大于它 分别对枢轴元素前面和后面的两段待排序列采用快速排序方法，直至每一段都只剩下一个元素为止 分治算法原理 分解：将原问题分解为若干子问题； 求解：递归地解各子问题，若子问题规模足够小，则直接求解 组合：将各子问题的解组合成原问题的解；,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49

21、用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、4

22、9 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27

23、、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、

24、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,快速排序,e.g:将序列 49、38、65、97、76、1

25、3、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76

26、、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、

27、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、9

28、7、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65

29、、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、

30、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、3

31、8、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49

32、、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列

33、49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序

34、列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序,若序列中有 n 个元素，任选一个关键字作为界点，将序列分成两部分。其中左半部分的结点的关键字小于等于界点，右半部分的结点的关键字大于等于界点。然后，对左右两部分分别进行类似的处理，直至排好序为止。,e.g:

35、将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,快速排序算法,void QuickSort() QSort(1, n); ,void QSort (int low, int high) if (low high) pivotloc = Partition(low, high); Qsort(low, pivotloc - 1); Qsort(pivotloc + 1, high); ,快速排序算法（续）,int Partition(int low, int high) pivotkey = rlow; while (low = pivotkey ) hig

36、h-; rlow = rhigh; while (low high ,快速排序分析,是交换排序方法里最快的一种排序，其时间复杂度为 O(nlogn)； 快速排序的效率不太稳定，在关键字均匀分布时，效率最高；在关键字有序时，效率将退化为 O( n2 ) ；改进算法： “三者取中法” 快速排序是不稳定排序。 栈的深度: 最好情况下为 O(log n) ，最坏情况下为 n 。 每次先对较短子序列排序能降低栈的最大深度到O(log n),简单选择排序,简单选择排序 是一种最简单的排序方法； 每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录，直至最后一个记录为止。 简单选择排序是不稳定排序，

37、时间复杂度为 O( n2 )。 简单选择排序记录移动次数少,void SelectSort(SqList ,简单选择排序举例 49 38 65 97 76 49 13 27 13 38 65 97 76 49 49 27 13 27 65 97 76 49 49 38 13 27 38 97 76 49 49 65 13 27 38 49 76 97 49 65 13 27 38 49 49 97 76 65 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 （每趟排序使有序区增加一个记录）,简单选择排序举例,锦标赛排序,树形选择排序 又称为锦标赛

38、排序，是一种按锦标赛思想进行的排序； 排序方法 将相邻记录两两分为一组进行比较，将关键字较小的记录送往上一层，参加与其它组关键字较小记录的比较，两两比较后再送往上层关键字较小记录，反复此过程，直到只剩下一个记录即为关键字最小记录； 将待排序列中该最小记录处置为无穷大，则与其比较过的所有记录按层次逐级比较，直至找到下一个最小记录为止；反复此过程直至序列有序。 树形选择排序除第一次外，每次都走了树的一条分支，故其时间复杂度为 O(n log n)。,23 23 40 38 23 40 46 38 23 38 40 性能 除第一次外，每次都走了树的一条分支，故其时间复杂度为O(n log2n)。 缺

39、陷 辅助空间较多；需与“无穷大值”进行多余的比较,23,38,38,38,38,46,38,38,38,46,40,40,46,46,稳定排序,锦标赛排序,堆排序,堆排序 堆的定义 n 个元素的序列 k1,k2,kn当且仅当满足下列关系时，称为堆： kik2i kik2i i=1,2,n/2 kik2i+1 kik2i+1 堆排序思路 建立在树形选择排序基础上 将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素； 将其与序列的最后一个元素交换，将序列长度减一； 再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列

40、长度； 反复此过程，直至序列长度为一，所得序列即为排序后结果。,或,堆排序举例,堆排序举例 待排记录的关键字 32，12，91，26，74，58，63，85 堆排序的结果为： 12，26，32，58，63，74，85，91。,堆排序算法实现,void HeapAdjust(int s, int m) rc = rs; for (j=2 * s; j rj) break; rs = rj; s = j; rs = rc; void HeapSort(HeapType ,堆排序特点,堆排序需要首先初始化堆(比较次数不超过4n)，然后,每次堆调整，排好一个元素(最多2*堆深度) 对记录数较大的文件很

41、有效 堆排序只需一个辅助空间用于交换，其时间复杂度为 O( nlog n ) 堆排序最坏情况下也是O(nlogn)性能 堆排序是不稳定排序,归并排序,归并排序 每次将两个或两个以上的有序表合并成一个较长的有序表，反复此过程，直到最终只剩下一个有序表为止；单个记录即是最初的有序表,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直

42、至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.

43、g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素

44、，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序

45、,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序,合并两个已排序的顺序表。 e.g: 将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,归并排序算法举例,49 38 65 97 31 76 13 27 98 53 21 12 88 74 43 87 16 55 38 49 65 97 31 76 13 27 53 98 12 21 74 88 43 87 16 55 38 49 65 97

46、 13 27 31 76 12 21 53 98 43 74 87 88 16 55 13 27 31 38 49 65 76 97 12 21 43 53 74 87 88 98 16 55 12 13 21 27 31 38 43 49 53 65 74 76 87 88 97 98 16 55 12 13 16 21 27 31 38 43 49 53 55 65 74 76 87 88 97 98,归并排序算法实现,Void Merge(int *SR, int *TR, int i, int m, int n) / 将 SRim , SRm+1n归并为 TRin for (j=m+1

47、, k=i; i=m ,归并排序算法实现,Void MSort(int *SR, int *TR, int *extra, int s, int t ) if (s = t) TRs = SRs; else m = (s + t) / 2 ; / 将SRst分为SRsm和SRm+1t Msort(SR, extra, TR, s, m); / 将SRsm归并为有序的extrasm Msort(SR, extra, TR, m+1, t); / 将SRm+1t归并为有序的extram+1t Merge(extra, TR, s, m, t); / 将extrasm和extram+1t 归并到TR

48、st ,Void MergeSort() / 将顺序表 L 进行归并排序 Msort(r, r, extra, 1, length); ,归并排序分析,任何情况时间复杂度O(nlog2n) 空间复杂度O(n),每趟都需要复制所有元素 稳定的排序方法 递归方式书写简单，但是实用性差，需改进成非递归算法。但算法显得不够简洁 很少用于内部排序,基数排序,借助多关键字排序的思想对单逻辑关键字进行排序 多关键字排序 如 52 张扑克牌按以下规则排成有序： 333344AA2222 牌点：决定大小的主要因素(3410JQKA2)； 花色： ，决定大小的次要因素；只有在牌点相同时，才起作用 牌点为高位关键字，花色为低位关键字，决定元素的大小主要看高位关键字，低位关键字只有在高位关键字相等时才发挥作用。 一般的，设有n个记录序列(R1,R2,