第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序

Presentation on theme: "第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序"— Presentation transcript:

1 第十章 内部排序 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 其他插入排序 10.2.3 希尔排序
第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序 10.3 快速排序 10.4 选择排序 简单选择排序 树形选择排序 堆排序 10.5 归并排序 10.7 各种内部排序方法的比较讨论

2 第十章 内部排序 目的： 讨论比较各种内部排序方法；
第十章 内部排序 目的： 讨论比较各种内部排序方法； 插入排序、交换排序、选择排序、归并排序等的基本思想、算法特点、排序过程以及它们的时间复杂度的分析 重点讨论性能先进的高效算法

3 第十章 内部排序 学习要点： 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用 了解各种内部排序方法的排序过程及其依据的原则
第十章 内部排序 学习要点： 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用 了解各种内部排序方法的排序过程及其依据的原则 掌握各种内部排序方法的时间复杂度的分析方法 理解排序方法“稳定”或“不稳定”的含义； 希尔排序、快速排序、堆排序和归并排序等高效算法

4 10.1 概述 一、什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“按关键字有序”的记录序列。
第十章 排序 10.1 概述 一、什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“按关键字有序”的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 为什么排序？ 有序的顺序表可以采用效率较高的折半查找法 无序的顺序表只能顺序查找

5 10.1 概述 排序的确切定义： 假设含n个记录的序列为 { R1, R2, …， Rn } (1) 其相应的关键字序列为
第十章 排序 10.1 概述 排序的确切定义： 假设含n个记录的序列为 { R1, R2, …， Rn } (1) 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Kp1≤Kp2≤…≤Kpn 按此固有关系将式(1)的记录序列重新排列为 { Rp1, Rp2, …，Rpn } 的操作称作排序。

6 第十章 排序 10.1 概述 排序的稳定： 1）上述排序中的关键字可以是主关键字，也可以是次关键字，如果是主关键字，则排序结果是唯一的；若是次关键字，排序结果可能不是唯一的 2）假设Ki=Kj(1<=i, j<=n, ij)，且在排序前的序列中Ri领先于Rj(即i<j)，若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的，否则是不稳定的。

7 10.1 概述 二、内部排序和外部排序 1）内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；
第十章 排序 10.1 概述 二、内部排序和外部排序 1）内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 2）外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

8 第十章 排序 10.1 概述 三、内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。 使有序区中记录的数目增加一个或几个的操作称为一趟排序。

9 10.1 概述 逐步扩大记录有序序列长度的方法大致有下列几类： 1. 插入类
第十章 排序 10.1 概述 逐步扩大记录有序序列长度的方法大致有下列几类： 1.  插入类 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度； 2. 交换类 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;

10 第十章 排序 10.1 概述 3. 选择类 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度; 4. 归并类 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度; 5. 其它方法（如基数排序） 下面将对每一类的排序算法介绍一至两个排序算法。

11 10.1 概述 排序中的基本操作： 1）比较关键字大小（对大多数的排序方法是必须的）；
第十章 排序 10.1 概述 排序中的基本操作： 1）比较关键字大小（对大多数的排序方法是必须的）； 2）移动记录（可以通过改变记录的存储方式来予以避免）。 排序评价标准 1）执行时间：比较次数、移动次数 2）所需附加空间 3）算法复杂程度

12 第十章 排序 10.1 概述 待排序记录的存储方式： 1）存放在地址连续的一组存储单元中，记录之间的关系由存储位置决定，排序必须移动记录——类似于线性表的顺序存储结构； 2）存在静态链表中，记录之间的关系由指针指示，排序不用移动记录，指向修改指针——类似于线性表的链式存储结构（链表排序）； 3）待排序记录本身存储在一组地址连续的存储单元内，同时附设一个指示记录存储位置的地址向量，排序过程中不移动记录，而移动地址向量中这些记录的地址，在排序结束后，再按照地址向量中的值调整记录的存储位置——地址排序。

13 10.1 概述 顺序存储结构 #define MAXSIZE 100 typedef int KeyType;
第十章 排序 10.1 概述 顺序存储结构 #define MAXSIZE 100 typedef int KeyType; typedef int DataType; typedef struct { KeyType key; DataType Info; } RecordNode; RecordNode record[MAXSIZE+1]; int length; /* 记录个数*/ } SqList;

14 10.2 插入排序 基本方法：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。 一、直接插入排序
第十章 排序 10.2 插入排序 基本方法：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。 一、直接插入排序 直接插入排序的基本思想：当插入第i (i  1) 个对象时，前面的R[0], R[1], …, R[i-1]已经排好序。这时，用R[i]的关键字与R[i-1], R[i-2], …的关键字顺序进行比较，找到插入位置即将R[i]插入，原来位置上的对象向后顺移。

15 10.2 插入排序 假设在排序过程中，记录序列R[1..n]的状态为：
第十章 排序 10.2 插入排序 假设在排序过程中，记录序列R[1..n]的状态为： 则一趟直接插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]，记录数增1。 显然，完成这个“插入”需分三步进行： 1．查找R[i]的插入位置j+1； 2．将R[j+1..i-1]中的记录后移一个位置； 3．将R[i]复制到R[j+1]的位置上。

16 10.2 插入排序 利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：
第十章 排序 10.2 插入排序 利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点： 1）从R[i-1]起向前顺序查找，监视哨设置在R[0]； R[0] = R[i]; // 设置“哨兵” for (j=i-1; R[0].key<R[j].key; --j); // 从后往前找 return j+1; // 返回R[i]的插入位置为j+1 2）对于在查找过程中找到的那些关键字不小于R[i].key的记录，在查找的同时实现向后移动； for (j=i-1; R[0].key<R[j].key; --j); R[j+1] = R[j]；

17 10.2 插入排序 3）i = 2，3，…, n, 实现整个序列的排序。
第十章 排序 10.2 插入排序 3）i = 2，3，…, n, 实现整个序列的排序。 void InsertSort ( SqList &R, int n) { // 对记录序列R[1..n]作直接插入排序。 for ( i=2; i<=n; ++i ) { R[0] = R[i]; // 复制为监视哨 for ( j=i-1; R[0].key < R[j].key; --j ) R[j+1] = R[j]; // 记录后移 R[j+1] = R[0]; // 插入到正确位置 } } // InsertSort

18 7．2 插入排序

19 10.2 插入排序 时间分析： 实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。
10.2 插入排序 时间分析： 实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： “移动”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： “移动”的次数：

20 10.2 插入排序 若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 空间效率：只需要一个记录的辅助空间。 算法特点：简洁、易实现，适用于待排序记录数量n很小时。

21 10.2 插入排序 二、折半插入排序（对分查找） 折半插入排序：因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。 其算法如下： void BInsertSort (SqList &R，int n) { // 对记录序列R[1..n]作折半插入排序。 for ( i=2; i<= n; ++i ) { R[0] = R[i]; // 将R[i]暂存到R[0] low = 1; high = i-1;

22 10.2 插入排序 while (low<=high) { //在R[low..high]中折半查找插入的位置
10.2 插入排序 while (low<=high) { //在R[low..high]中折半查找插入的位置 mid = (low+high)/2; // 折半 if (R[0].key < R[mid].key)) high = mid-1; // 插入点在低半区 else low = mid+1; } // 插入点在高半区 for ( j=i-1; j>=high+1; --j ) R[j+1] = R[j]; // 记录后移 R[high+1] = R[0]; // 插入 } } // BInsertSort

23 10.2 插入排序 性能分析： 空间效率：同直接插入排序
10.2 插入排序 性能分析： 空间效率：同直接插入排序 时间效率：比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。时间复杂度为 o(n2)。 折半插入排序是一个稳定的排序方法。

24 10.2 插入排序 三、2-路插入排序 在折半插入排序的基础上的进一步改进 目的：减少排序过程中移动记录的次数，需要n个记录的辅助空间
10.2 插入排序 三、2-路插入排序 在折半插入排序的基础上的进一步改进 目的：减少排序过程中移动记录的次数，需要n个记录的辅助空间 具体做法：设置一个辅助数组d[n]，第一个记录放在d[1]中，并把该数组看成是一个环形的，以d[1]为界，分别在两端进行插入排序。 优点：可以使记录移动次数减少一半。

25 10.2 插入排序 五、希尔排序 (Shell Sort)
10.2 插入排序 五、希尔排序 (Shell Sort) 希尔排序方法又称为缩小增量排序。该方法的基本思想是：设待排序对象序列有 n 个对象，首先取一个整数 gap < n 作为间隔，将全部对象分为 gap 个子序列，所有距离为 gap 的对象放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap，例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1，将所有对象放在同一个序列中排序为止。

26 10.2 插入排序

27 10.2 插入排序

28 10.2 插入排序

29 10.2 插入排序 开始时gap的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。 Gap的取法有多种： 最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 后来knuth 提出取gap = gap/3 +1。 还有人提出都取奇数为好，也有人提出各gap互质为好。

30 算法: Void shellsort(RecType R[],int n) {Int i,j,d;RecType temp;
Gap=n/2; While(Gap>0) {for( i=Gap;i<n;i++) {j=i-Gap; while(j>=0&&R[j}.key>R[j+Gap].key) {temp=R[j]; R[j]=R[j+Gap]; R[j+d]=temp; j=j-Gap; } Gap/=2; }}

31 10.2 插入排序 算法分析 对特定的待排序对象序列，可以准确地估算关键字的比较次数和对象移动次数。
10.2 插入排序 算法分析 对特定的待排序对象序列，可以准确地估算关键字的比较次数和对象移动次数。 但想要弄清关键字比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出，当 n 很大时，关键字平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

32 10.3 快速排序 一类籍助“交换”进行排序的方法 交换排序的基本思想：两两比较待排序对象的关键字，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都排好序为止。 最简单的一种交换排序是：起泡排序

33 10.3 快速排序 一、起泡排序 假设在排序过程中，记录序列R[1..n]的状态为： n-i+1
10.3 快速排序 一、起泡排序 假设在排序过程中，记录序列R[1..n]的状态为： 则第i趟起泡插入排序的基本思想为：借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。 n-i+1

34 10．3 交换排序 2．冒泡排序的算法实现 void Bubblesort( NODE array[],int n) { int i, j, flag; //当flag为0则停止排序 NODE temp; for ( i=1; i<n; i++) // i 表示趟数，最多n-1趟 { flag=0; //开始时元素未交换 for ( j=n-1; j>=i; j--) if (array[j].key<array[j-1].key) //发生逆序 temp=array[j];array[j]=array[j-1];array[j-1]=temp; flag=1; } //交换，并标记发生了交换 if(flag==0) break; } }

35 10.3 快速排序 起泡排序的结束条件为：最后一趟没有进行“交换”。 时间分析: 最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡
10.3 快速排序 起泡排序的结束条件为：最后一趟没有进行“交换”。 时间分析: 最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡 “比较”的次数： “移动”的次数： 最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡

36 10.3 快速排序 起泡排序需要一个附加对象以实现对象值的对换。 起泡排序是一个稳定的排序方法。
10.3 快速排序 起泡排序需要一个附加对象以实现对象值的对换。 起泡排序是一个稳定的排序方法。 从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 试设想，若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。 

37 10．3 交换排序 快速排序 1．快速排序的基本思想 快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。

38 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。
10．3 交换排序 快速排序的过程为：把待排序区间按照第一个元素（即基准元素）的排序码分为左右两个子序列的过程叫做一次划分。设待排序序列为array[start]～array[end]，其中start为下限，end为上限，start＜end，mid=array[start]为该序列的基准元素，为了实现一次划分，令i,j的初值分别为start和end。在划分过程中，首先让j从它的初值开始，依次向前取值，并将每一元素array[j]的排序码同mid的排序码进行比较，直到array[j].key<mid.key时，交换array[j]与array[i]的值，使排序码相对较小的元素交换到左子序列，然后让i从i＋1开始，依次向后取值，并使每一元素array[i]的排序码同array[j]的排序码（此时array[j]为基准元素）进行比较，直到array[i]＞array[j]时，交换array[i]与array[j]的值，使排序码大的元素交换到后面子区间；再接着让j从j-1开始，依次向前取值，重复上述过程，直到i等于j,即指向同一位置为止，此位置就是基准元素最终被存放的位置。此次划分得到的前后两个待排序的子序列分别为array[start]～array[i-1]和array[i+1]～array[end]。 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。

39 10．3 交换排序

40 10．3 交换排序 从图7-4可知，通过一次划分，将一个区间以基准值分成两个子区间，左子区间的值小于等于基准值，右子区间的值大于基准值。对剩下的子区间重复此划分步骤，则可以得到快速排序的结果。 2．快速排序的算法实现 下面给出快速排序算法的递归算法如下：

41 10．3 交换排序 void quicksort(NODE array[],int start , int end) { int i , j; NODE mid; if (start>=end) return; i=start;j=end;mid=array[i]; while (i<j) { while (i<j && array[j].key>mid.key) j--; if (i<j) {array[i]=array[j]; i++; } while (i<j && array[i].key<=mid.key) i++; if (i<j) {array[j]=array[i]; j--; } } //一次划分得到基准值的正确位置 array[i]=mid; quicksort(array,start,i-1); //递归调用左子区间 quicksort(array,i+1,end); }//递归调用右子区间

42 10．3 交换排序 3．快速排序的效率分析 若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2n<h<log2n+1 ，所以总的比较次数不会超过(n+1) log2n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1≤i≤n）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。 快速排序是一种不稳定的排序方法。

43 10.4 选择排序 选择排序的基本思想是：每一趟 (例如第 i 趟，i = 0, 1, …, n-2) 在后面 n-i 个待排序对象中选出关键码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-2 趟作完，待排序对象只剩下1个，就不用再选了。 其中最简单的一种为简单选择排序。

44 10.4 选择排序 一、简单选择排序 假设排序过程中，待排记录序列的状态为：
10.4 选择排序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟简单选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列。

45 10.4 选择排序 它的基本步骤是： 在一组对象R[i]～R[n-1]中选择具有最小关键字的对象；
10.4 选择排序 它的基本步骤是： 在一组对象R[i]～R[n-1]中选择具有最小关键字的对象；  若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调； 在这组对象中剔除这个具有最小关键字的对象，在剩下的对象R[i+1]～R[n-1]中重复执行第、步，直到剩余对象只有一个为止。

46 10.4 选择排序

47 10.4 选择排序

48 10.4 选择排序

49 10.4 选择排序

50 10.4 选择排序 简单选择排序的算法描述如下： void SelectSort (SqList &R, int n ) {
10.4 选择排序 简单选择排序的算法描述如下： void SelectSort (SqList &R, int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i<n; ++i) { // 选择第i小的记录，并交换到位 j = SelectMinKey(R, i); // 在R[i..n]中选择key最小的记录 if (i!=j) R[i]←→R[j]; // 与第i个记录交换 } } // SelectSort

51 10.4 选择排序 时间性能分析 对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为
10.4 选择排序 时间性能分析 对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为 移动记录的次数，最小值为0, 最大值为3(n-1) 直接选择排序是一种不稳定的排序方法。

52 10.4 选择排序 二、树形选择排序（锦标赛排序，(Tournament Tree Sort)
10.4 选择排序 二、树形选择排序（锦标赛排序，(Tournament Tree Sort) 思想：与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两比较，…，如此重复，直到选出一个关键字最小的对象为止。

53 10.4 选择排序 在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。

54 10.4 选择排序 如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 < n  2k 的2k个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。

55 10.4 选择排序 胜者树的概念 每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。
10.4 选择排序 胜者树的概念 每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。 位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放对象的关键字 data 外，还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号index。 胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。

56 10.4 选择排序 形成初始胜者树（最小关键字上升到根） 关键字比较次数 : 6

57 10.4 选择排序 输出冠军并调整胜者树后树的状态 关键字比较次数 : 2

58 10.4 选择排序 输出亚军并调整胜者树后树的状态 关键字比较次数 : 2

59 10.4 选择排序 输出第三名并调整胜者树后树的状态 关键字比较次数 : 2

60 10.4 选择排序 输出第四名并调整胜者树后树的状态 关键字比较次数 : 2

61 10.4 选择排序 全部比赛结果输出时树的状态 关键字比较次数 : 2

62 10.4 选择排序 锦标赛排序构成的树是满的完全二叉树，其深度为 log2(n+1)，其中 n 为待排序元素个数。
10.4 选择排序 锦标赛排序构成的树是满的完全二叉树，其深度为 log2(n+1)，其中 n 为待排序元素个数。 除第一次选择具有最小关键字的对象需要进行 n-1 次关键字比较外，重构胜者树选择具有次小、再次小关键字对象所需的关键字比较次数均为 O(log2n)。总关键字比较次数为O(nlog2n)。 对象的移动次数不超过关键字的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。 这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。

63 10.4 选择排序 如果有 n 个对象，必须使用至少 2n-1 个结点来存放胜者树。最多需要找到满足 2k-1 < n  2k 的k，使用 2*2k-1 个结点。每个结点包括关键字、对象序号和比较标志三种信息。 锦标赛排序是一个稳定的排序方法。

64 10.4 选择排序 三、堆排序 堆排序的特点：在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。
10.4 选择排序 三、堆排序 堆排序的特点：在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。 堆的定义：满足下列性质的数列{r1, r2, …，rn}： 或 若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。

65 10.4 选择排序 由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
10.4 选择排序 由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。   例：{96，83，27，38，11，09} {12，36，24，85，47，30，53，91} 12 24 30 47 85 36 53 91 96 27 09 11 38 83

66 10.4 选择排序 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。
10.4 选择排序 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。

67 10.4 选择排序 现在剩下两个问题： （1）如何由一个无序序列建成一个堆； （2）如何在输出堆顶元素后，调整剩余元素成为一个新的堆。
10.4 选择排序 现在剩下两个问题： （1）如何由一个无序序列建成一个堆； （2）如何在输出堆顶元素后，调整剩余元素成为一个新的堆。 在输出堆顶元素后，用堆中最后一个元素替代，此时根结点的左右子树均为堆，则仅需自上而下进行调整即可。

68 10.4 选择排序 “筛选”：首先堆顶元素和其左右孩子的值比较，把最小的值（假设为左孩子结点）调到根结点的位置，由于左子树的根结点发生了改变，因此需要对左子树进行上述一样的调整，直至叶子结点。这个自堆顶至叶子的调整过程称为“筛选”。 从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此无序序列看成是一个完全二叉树，则最后一个非终端结点就是第n/2 个元素，因此筛选只需从第n/2 个元素起，筛选到第1个元素（即堆顶元素）。

69 10.4 选择排序

70 10.4 选择排序 建立初始的最大堆

71 10.4 选择排序

72 10.4 选择排序

73 10.4 选择排序

74 10.4 选择排序

75 10.4 选择排序

76 10.4 选择排序

77 10.4 选择排序 堆排序的算法如下所示： void HeapSort ( SqList R[], int n ) {
10.4 选择排序 堆排序的算法如下所示： void HeapSort ( SqList R[], int n ) { // 对记录序列R[1..n]进行堆排序。 for ( i=n/2; i>0; --i ) // 把R[1..n]建成大顶堆 HeapAdjust ( R, i, n ); for ( i=n; i>1; --i ) { R[1]←→R[i]; // 将堆顶记录和当前未经排序子序列R[1..i]中最后一个记录相互交换 HeapAdjust(R, 1, i-1); } //将R[1..i-1] 重新调整为大顶堆 } // HeapSort

78 10.4 选择排序 其中筛选的算法如下。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。
10.4 选择排序 其中筛选的算法如下。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。 void HeapAdjust (SqList R[], int s, int m) { //已知R[s..m]中记录的关键字除R[s].key之外均满足堆的定义，本函数调整R[s] 的关键字，使R[s..m]成为一个大顶堆（对其中记录的关键字而言） rc = R[s]; for ( j=2*s; j<=m; j*=2 ) { // 沿key较大的孩子结点向下筛选

79 10.4 选择排序 if ( j<m && R[j].key<R[j+1].key ) ++j;
10.4 选择排序 if ( j<m && R[j].key<R[j+1].key ) ++j; // j为key较大的记录的下标 if ( rc.key >= R[j].key ) break; // rc应插入在位置s上 R[s] = R[j]; s = j; } R[s] = rc; // 插入 } // HeapAdjust

80 10.4 选择排序 堆排序的时间复杂度分析： 1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);
10.4 选择排序 堆排序的时间复杂度分析： 1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1); 2．对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n; 3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过 2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n) 因此，堆排序的时间复杂度为O(nlogn)

81 10.5 归并排序 基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。
归并排序 基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列R[l..m]和R[m+1..n] 归并为一个有序序列R[l..n]

82 归并排序 2-路归并排序的基本思想：设两个有序表A和B的对象个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。 当 i 和 j 都在两个表的表长内变化时，根据A[i]与B[j]的关键码的大小，依次把关键码小的对象排放到新表C[k]中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表C[k]中。

83 归并排序 “归并”算法描述如下： void Merge (SqList SR[], SqList TR[], int i, int m, int n) {// 将有序的SR[i..m]和SR[m+1..n]归并为序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { // 将SR中记录由小到大地并入TR if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i<=m) TR[k..n] = SR[i..m]; // 将剩余的SR[i..m]复制到TR if (j<=n) TR[k..n] = SR[j..n]; // 将剩余的SR[j..n]复制到TR } // Merge

84 10.5 归并排序 归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。
归并排序 归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。 这是一种自顶向下的分析方法： 如果记录无序序列R[s..t]的两部分R[s..(s+t)/2]和R[(s+t)/2+1..t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。

85 10.5 归并排序 void Msort (SqList SR[], SqList TR1[], int s, int t) {
归并排序 void Msort (SqList SR[], SqList TR1[], int s, int t) { // 将SR[s..t]进行2-路归并排序为TR1[s..t]。 if (s==t) TR1[s] = SR[s]; else { m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t] Msort (SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] Msort (SR, TR2, m+1, t); //递归地SR[m+1..t]归并为有序的TR2[m+1..t] Merge (TR2, TR1, s, m, t); } // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] } // MSort

86 10.5 归并排序 void MergeSort (SqList R[]) { // 对记录序列R[1..n]作2-路归并排序。
归并排序 void MergeSort (SqList R[]) { // 对记录序列R[1..n]作2-路归并排序。 MSort(R, R, 1, n); } // MergeSort 容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。

87 归并排序

88 10.6 各种排序方法的综合比较 一、时间性能 1. 按平均的时间性能来分，有三类排序方法：
10.6 各种排序方法的综合比较 一、时间性能  1.    按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好； 时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。

89 10.6 各种排序方法的综合比较 2. 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

90 10.6 各种排序方法的综合比较 二、空间性能 指的是排序过程中所需的辅助空间大小。
10.6 各种排序方法的综合比较 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n); 4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。 

91 10.6 各种排序方法的综合比较 三、排序方法的稳定性能
10.6 各种排序方法的综合比较 三、排序方法的稳定性能 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 对于不稳定的排序方法，只要能举出一个实例说明即可。 快速排序和堆排序是不稳定的排序方法。

92 10.5 各种排序方法的综合比较 四、关于“排序方法的时间复杂度的下限”
10.5 各种排序方法的综合比较 四、关于“排序方法的时间复杂度的下限” 本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。 可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。

93 10.5 各种排序方法的综合比较

94 小 结 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 附加存储 插入排序
小 结 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 附加存储 插入排序 用事例表明直接插入排序、折半插入排序的过程 直接插入排序和折半插入排序的算法排序的性能分析 当待排序的关键字序列已经基本有序时，用直接插入排序最快

95 小 结 选择排序 用事例表明直接选择排序、锦标赛排序、堆排序的过程 直接选择排序和堆排序的算法 三种选择排序的性能分析
小 结 选择排序 用事例表明直接选择排序、锦标赛排序、堆排序的过程 直接选择排序和堆排序的算法 三种选择排序的性能分析 用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。 当在 n 个数据（n很大）中选出最小的 5  8 个数据时，锦标赛排序最快。

96 小 结 锦标赛排序算法将待排序数据个数 n 补足到 2的 k 次幂 2k-1 < n  2k
小 结 锦标赛排序算法将待排序数据个数 n 补足到 2的 k 次幂 2k-1 < n  2k 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。 交换排序 用事例表明起泡排序和快速排序的过程 起泡排序的算法 快速排序的递归算法 快速排序是一个递归的排序法 当待排序关键码序列已经基本有序时，快速排序显著变慢。

97 小 结 二路归并排序 用事例表明二路归并排序的过程 二路归并排序的非递归算法 该算法的性能分析 归并排序可以递归执行
小 结 二路归并排序 用事例表明二路归并排序的过程 二路归并排序的非递归算法 该算法的性能分析 归并排序可以递归执行 归并排序需要较多的附加存储。 归并排序对待排序关键码的初始排列不敏感，故排序速度较稳定。

98 作 业 1．以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，执行以下排序算法，写出每一趟排序结束时的关键码状态“ （1）直接插入排序；（2）希尔排序（增量d[1]=5）; （3）快速排序；（4）堆排序；（5）归并排序。 2．实现以下排序算法： （1）冒泡排序；（2）希尔排序；（3）快速排序。