数据结构 第10章 内部排序.

Presentation on theme: "数据结构 第10章 内部排序."— Presentation transcript:

1 数据结构 第10章 内部排序

2 第10章 内部排序 10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序
10.7 各种内部排序方法的比较讨论

3 10.1 概述 什么是“排序”？ 排序是将无序的记录序列调整为有序记录序列的一种操作。
排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。

4 10.1 概述 排序： 内排序与外排序 内部排序：全部记录都可以同时调入内存进行的排序。
外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。 内排序与外排序

5 10.1 概述 定义： 设有记录序列：{ R1、R2 ……….. Rn } 其相应的关键字序列为：
{ K1、K2 ……….. Kn }; 若存在一种确定的关系： Kx <= Ky <= … <= Kz 则将记录序列 { R1、R2 ……….. Rn } 排成按该关键字有序的序列： { Rx、Ry ……….. Rz } 的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。 排序的确切定义 使一组任意排列的记录变成一组按关键字线性有序的记录。

6 10.1 概述 稳定与不稳定： 若记录序列中的任意两个记录 Rx、Ry 的关键字 Kx = Ky ；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。 如 2, 2,1，排序后若为1, 2, 2 则该排序方法是不稳定的。

7 10.1 概述 排序的时间开销 是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。
评价排序算法好坏的标准主要有两条： 算法执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑的一个因素。 排序算法所需要的附加空间一般都不大，矛盾并不突出。而排序是一种经常执行的一种运算，往往属于系统的核心部分，因此排序的时间开销是算法好坏的最重要的标志。

8 10.1 概述 按排序过程中依据的不同原则对内部排序方法进行分类： 插入排序 交换排序 选择排序 归并排序 基数排序

9 10.1 概述 待排序的记录序列可以用顺序表表示，也可以用链表表示。本章讨论的排序算法一律以顺序表为操作记录。

10 10.1 概述 const MAXSIZE = 20; // 假设的顺序表最大长度 typedef struct {
　　RcdType r[MAXSIZE+1]; 　　// r[0]闲置或作为判别标志的"哨兵"单元 　　int length; 　　　// 顺序表长度 　} SqList；　　　　　// 顺序表类型 其中记录类型定义为： 　　KeyType key; 　　　　　// 关键字项 　　InfoType otherinfo;　　 // 其它数据项　 　} RcdType; // 记录类型并设定关键字为整型 　typedef int KeyType;

11 10.2 插入排序 基本原理，每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录适当位置上，直到记录全部插入为止。
直接插入排序 其它插入排序 希尔排序

12 直接插入排序 基本思想： 当插入第i个对象时，前面的V[1],V[2],…,V[i-1]已经排好序，此时，用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。

13 直接插入排序 例： 49] 38 49] ] ] ] ] 27 49 ] 49 ]

14 10.2.1 直接插入排序 显然，只含一个记录的序列是有序的，因此令 i 从2起，逐个插入直到 n 便可实现整个插入排序，算法如下：
void InsertSort ( SqList &L) { 　　// 对顺序表L作直接插入排序 　　for ( i=2; i<=L.length; ++i ) 　　　if ( L.r[i].key < L.r[i-1].key ) { // 将 L.r[i] 插入有序子表 　　　　L.r[0] = L.r[i]; 　　　　L.r[i] = L.r[i-1]; 　　　　for ( j=i-2; L.r[0].key < L.r[j].key; --j ) 　　　　　L.r[j+1] = L.r[j]; 　　　　　　// 记录后移 　　　　L.r[j+1] = L.r[0]; 　　　　　　　// 插入到正确位置 　　　} // if } // InsertSort

15 10.2.1 直接插入排序 另外一种实现： void InsertSort ( SqList &L) { // 对顺序表L作直接插入排序
for (i=2; i<=L.length; i++) { L.r[0]＝L.r[i]; j＝i-1; while (L.r[0].key<L.r[j].key) L.r[j+1]＝L.r[j--]; L.r[j+1]＝L.r[0]; } } // InsertSort

16 直接插入排序 算法中引入附加记录r[0]有两个作用：其一是进入查找循环之前，它保存了r[i]的副本，使得不至于因记录的后移而丢失r[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），r[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。因此，我们把r[0]称为“监视哨”。

17 10.2.1 直接插入排序 直接插入排序的时间复杂度 从上述排序过程可见，排序中的两个基本操作是：（关键字间的）比较和（记录的）移动。
因此排序的时间性能取决于排序过程中这两个操作的次数。 从直接插入排序的算法可见，这两个操作的次数取决于待排记录序列的状态，当待排记录处于"正序"(即记录按关键字从小到大的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于"逆序"(即记录按关键字从大到小的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最多

18 直接插入排序 直接插入排序的时间复杂度 若待排记录序列处于随机状态，则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度。一般情况下，直接插入排序的时间复杂度为O (n2)。 待排记录序列状态 "比较"次数 "移动"次数 正序 n-1 逆序 (n+2)(n-1)/2 (n+4)(n-1)/2

19 10.2.1 直接插入排序 直接插入排序的稳定性： 直接插入排序是一种稳定的排序方法。
原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。

20 其它插入排序 折半插入排序 2-路插入排序 表插入排序

21 折半插入排序 由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用"折半查找"查询插入位置，由此得到的插入排序算法为"折半插入排序"。

22 折半插入排序 算法如下： void BInsertSort (SqList &L) { // 对顺序表L作折半插入排序
　　for ( i=2; i<=L.length; ++i ) { 　　　L.r[0] = L.r[i];　　　　　　　　　　　　　　// 将L.r[i]暂存到L.r[0] 　　　low = 1; high = i-1; 　　　while (low<=high) { 　　　　　　　　　　　// 在r[low..high]中折半查找有序插入的位置 　　　　m = (low+high)/2; 　　　　　　　　　　　　// 折半 　　　　if (L.r[0].key < L.r[m].key)) high = m-1; 　// 插入点在低半区 　　　　else low = m+1; 　　　　　　　　　　　　　// 插入点在高半区 　　　} // while 　　　for ( j=i-1; j>=low; --j ) L.r[j+1] = L.r[j]; // 记录后移 　　　L.r[high+1] = L.r[0];　　　　　　　　　　　　// 插入 　　} 　} // BInsertSort

23 折半插入排序 折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O (n2)。

24 2-路插入排序 2-路插入排序 是在折半插入排序的基础上的改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

25 2-路插入排序 具体的做法： 另设一个和L.r同类型的数组d， 首先将L.r[1]赋值给d[1]，并将d[1]看成是在排好序的序列中处于中间位置的记录， 然后从L.r中第2个记录开始起依次插入到d[1]之前或之后的有序序列中。 现将待插记录的关键字和d[1]比较，若L.r[i].key<d[1].key，则将L.r[i]插入到d[1]之前的有序表中。反之，则将L.r[i]插入到d[1]之后的有序表中。

26 2-路插入排序 例： d: [49] 49] [38 49 65] [38 ] [38 ] [38 ] [13 38 ] [ ] [

27 2-路插入排序 在实现算法时，可将d看成是一个循环向量，并设两个指针first和last分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。 在2-路插入排序中，移动记录的次数约为n2/8，因此它只能减少移动记录的次数，而不能绝对避免移动记录。

28 表插入排序 由于插入排序的基本作法是将待排记录逐个插入到一个有序的记录序列中，在顺序表中实现插入就不可避免要移动记录。因此若想减少排序过程中移动记录所花时间，只有采用链表作存储结构才行。 但是排序的目的是为了使用以查找的记录序列是一个有序序列，以便可以进行折半查找，因此只能是在排序过程中将它视作链表，即在排序过程中以"修改指针"替代"移动记录"实现"插入"，排序的结果仍使记录序列按关键字有序。此时的链表由结点（记录+指针）的数组实现。

29 表插入排序 表插入排序是以静态链表作待排记录序列的存储结构实现的插入排序。这个静态链表由存储记录的顺序表和附加的指针数组构成，静态链表中的指针实际上指的是数组的下标。 表插入排序分两步进行：首先构造一个有序链表；然后按照"附加指针"的指示将结点中的记录重新排列成一个有序序列。

30 表插入排序 #define SIZE 100 typedef struct{ RcdType rc; int next; }SLNode;
SLNode r[size]; int length; }SLinkListType;

31 表插入排序 表插入排序实例： MAXINT 49 38 65 97 76 13 27 1 - MAXINT 49 38 65 97 76
- MAXINT 49 38 65 97 76 13 27 2 1 - MAXINT 49 38 65 97 76 13 27 2 3 1 - …………………………………… MAXINT 49 38 65 97 76 13 27 6 8 1 5 4 7 2 3

32 表插入排序 重排记录： void Arrange (SqList &L，int Next[] ) {
　　// 根据Next[]中的指针值调整记录位置，使得L中记录 　　// 按关键字非递减有序顺序排列 　　p = Next[0];　　　　　　　 // p 指示第一个记录的当前位置 　　for ( i=1; i<L.length; ++i ) 　　{ 　　　　　　　　　　　　　// SL.r[1..i-1]中记录已按关键字有序排列， 　　　　　　　　　　　　　　　　// 第 i 个记录 在L中的当前位置应不小于 i 　　　while (p<i) p = Next[p]; // 找到第i个记录，并用p指示其在L中当前位置 　　　q = Next[p]; 　　　　　　// q 指示尚未调整的后继记录 　　　if ( p!= i ) { 　　　　L.r[p]←→L.r[i];　　　// 交换记录，使第 i 个记录到位 　　　　Next[i] = p; 　　　// 指向被移走的记录，使以后可由while循环找回 　　　} // if 　　　p = q;　　　　　　　　 // p 指向下一个将要调整的记录 　　} // for } // Arrange

33 表插入排序 可以看出，在重排过程中至多进行3(n-1)次移动记录，然而整个表插入排序过程也仅仅是减少了移动记录的时间，所以它的时间复杂度仍为O (n2)。

34 10.2.3 希尔排序 1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。
基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。

35 希尔排序 希尔排序的基本过程 设待排序的对象序列有n个对象，首先取一个整数gap<n作为间隔，将全部对象分为gap个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。

36 希尔排序 例： [ ] (gap 5) [ ] [ ] [ ] (gap 3) [ ] [ ] (gap 1)

37 10.2.3 希尔排序 void ShellInsert ( SqList &L，int dk) {
　　// 对顺序表L作一趟增量为dk的希尔排序 　　for ( i=dk+1; i<=L.length; ++i ) 　　　if ( L.r[i].key < L.r[i-dk].key ) { // 将L.r[i]插入有序子表 　　　　L.r[0] = L.r[i]; L.r[i]=L.r[i-dk]; 　　　　for ( j=i-2*dk; j>0 && L.r[0].key < L.r[j].key; j-=dk ) 　　　　　L.r[j+dk] = L.r[j]; 　　　　　　// 记录后移 　　　　L.r[j+dk] = L.r[0]; 　　　　　　　// 插入到正确位置 　　　} // if 　} // ShellInsert void ShellSort (SqList &L, int dlta[], int t)　{ 　　// 按增量序列 dlta[0..t-1] 对顺序表L作希尔排序 　　for (k=0; k<t; ++t) 　　　ShellInsert(L, dlta[k]); // 一趟增量为 dlta[k] 的插入排序 　} // ShellSort

38 希尔排序 由于希尔排序在前几趟的排序过程中，关键字较大的记录是“跳跃式”地往后移动，从而使得在进行最后一趟插入排序之前序列中记录的关键字已基本有序，只需作少量关键字比较和移动记录，由此减少了整个排序过程中所需进行的“比较”和“移动”的次数。

39 10.2.3 希尔排序 希尔排序中gap的取法 Shell最初的方案是 gap= n/2, 直到gap=1.
Knuth的方案是gap = gap/3+1 其它方案有：都取奇数为好；或gap互质为好等等。

40 希尔排序 希尔排序的时间复杂度 对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。 Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。

41 希尔排序 希尔排序的稳定性 希尔排序是一种不稳定的排序方法。

42 10.3 快速排序 交换排序 基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。 两种常见的交换排序
起泡排序(Bubble Sort) 快速排序(Quick Sort)

43 起泡排序(Bubble Sort) 起泡排序的基本过程
在第i趟起泡排序之前，区段 R[n-i+2..n] 中的记录已按关键字从小到大有序排列，而区段 R[1..n-i+1] 中的记录不一定有序，但该区段中所有记录的关键字均不大于有序序列中记录的关键字(即小于或等于R[n-i+2].key)，则第i趟起泡排序的操作为， 从第1个记录起，逐个和相邻记录的关键字进行比较，若第j(1≤j≤n-i)个记录的关键字大于第j+1个记录的关键字，则互换记录，由此可将区段 R[1..n-i+1] 中关键字最大的记录“交换”到 R[n-i+1] 的位置上，从而使有序序列的长度增1。 显然，如果第i趟起泡排序的过程中，没有进行任何记录的交换，则表明区段 R[1..n-i+1] 中的记录已经按关键字从小到大有序排列，由此不再需要进行下一趟的起泡，即起泡排序已经完成，可见排序结束的条件是(i=n-1)或者（第i趟的起泡中没有进行记录交换）.

44 起泡排序(Bubble Sort) 例：

45 起泡排序(Bubble Sort) void BubbleSort(SqList &L) { // 对顺序表L作起泡排序
　　for (i=L.length, change=TRUE; i>1 && change; --i) { 　　　change = FALSE; 　　　for (j=1; j<i; ++j) 　　　　if (L.r[j].key > L.r[j+1].key) 　　　　　{ L.r[j]←→L.r[j+1]; change = TRUE } 　　}// for i 　} // BubbleSort

46 起泡排序(Bubble Sort) 分析起泡排序的时间复杂度： 和直接插入相似，排序过程中所进行的"比较" 和 "移动" 操作的次数取决于待排记录序列的状态，在待排记录处于"正序"时取最小值，此时只需进行一趟起泡排序，反之，在待排记录处于"逆序"时取最大值，此时需进行 n-1趟起泡，列表如下： 待排记录状态 "比较"次数 "移动"次数 正序 n-1 逆序 n(n-1)/2 3n(n-1)/2

47 起泡排序(Bubble Sort) 在一趟起泡的过程中，有可能只是在区段的前端进行记录的交换，而其后端记录已经按关键字有序排列，由此应在算法中设置一个指示“最后一个进行交换的记录的位置”的变量。改进后的起泡算法如下： void BubbleSort( SqList &L )　{　　// 对顺序表L作起泡排序 　　i = L.length; 　　while (i >1) { 　　　　　　　// i>1 表明上一趟曾进行过记录的交换 　　　lastExchangeIndex = 1; 　　　for (j = 1; j < i; j++){ 　　　　if (L.r[j+1].key < L.r[j].key) { 　　　　　L.r[j] ←→.r[j+1]； 　　　// 互换记录 　　　　　lastExchangeIndex = j; 　　// 记下进行交换的记录的位置 　　　　} // if 　　　} // for 　　　i = lastExchangeIndex; 　　　　　　　// 一趟起泡后仍处于无序状态的最后一个记录的位置 　　} // while 　} // BubbleSort

48 起泡排序(Bubble Sort) 起泡排序方法是稳定的

49 快速排序(Quick Sort) 快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。
其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。

50 快速排序(Quick Sort) 快速排序示例 49 38 65 97 76 13 27 49’ 38 65 97 76 13 27 49’
temp 27 38 65 97 76 13 49’ 27 38 97 76 13 65 49’ 27 38 13 97 76 65 49’ 27 38 13 76 97 65 49’ 27 38 13 49 76 97 65 49’

51 快速排序(Quick Sort) void QSort (RcdType R[], int s, int t ) {
　　// 对记录序列 R[s..t] 进行快速排序 　　if (s < t) { 　　　　　　　// 长度大于1 　　　pivotloc = Partition(R, s, t); 　　　　　　　　 // 对 R[s..t] 进行一趟快排，并返回枢轴位置 　　　QSort(R, s, pivotloc-1); // 对低子序列递归进行排序 　　　QSort(R, pivotloc+1, t); // 对高子序列递归进行排序 　　} // if } // Qsort void QuickSort( SqList & L) 　{ 　　// 对顺序表 L 进行快速排序 　　QSort(L.r, 1, L.length); } // QuickSort

52 快速排序(Quick Sort) 一趟快排也称“一次划分”，即将待排序列 R[s..t]“划分”为两个子序列R[s..i-1] 和 R[i+1..t]，i 为一次划分之后的枢轴位置。可以取待排序列中任何一个记录作为枢轴，但为方便起见，通常取序列中第一个记录 R[s] 为枢轴，以它的关键字作为划分的依据。 划分可如下进行：设置两个指针 low 和 high，分别指向待排序列的低端 s 和高端 t。 若R[high].key<R[s].key，则将它移动至枢轴记录之前；反之，若 R[low].key>R[s].key，则将它移动至枢轴记录之后，并为避免枢轴来回移动，可先将枢轴 R[s] 暂存在数组的闲置分量 R[0] 中。

53 快速排序(Quick Sort) int Partition ( RcdType R[], int low, int high) {
　　// 对记录子序列 R[low..high] 进行一趟快速排序，并返回枢轴记录 　　// 所在位置，使得在它之前的记录的关键字均不大于它的关键字， 　　// 而在它之后的记录的关键字均不小于它的关键字 　　R[0] = R[low];　　　　　　　　　　　// 将枢轴记录移至数组的闲置分量 　　pivotkey = R[low].key; 　　　　　　　// 枢轴记录关键字 　　while (low<high) {　　　　　　　　　// 从表的两端交替地向中间扫描 　　　while (low<high && R[high].key>=pivotkey) 　　　　--high; 　　　R[low++] = R[high];　　　　　　　// 将比枢轴记录小的记录移到低端 　　　while (low<high && R[low].key<=pivotkey) 　　　　++low; 　　　R[high--] = R[low];　　　　　　　// 将比枢轴记录大的记录移到高端 　　} // while 　　R[low] = R[0];　　　　　　　　　　　// 枢轴记录移到正确位置 　　return low; 　　　　　　　　　　　　// 返回枢轴位置 　} // Partition

54 快速排序(Quick Sort) 可以推证，快速排序的平均时间复杂度为 O (nlogn)，在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法. 如果借用起泡排序中设置记录"交换与否"的布尔变量的作法，快速排序也适用于已经有序的记录序列

55 快速排序(Quick Sort) 时间复杂性分析:
考虑平均情况下的时间复杂性。设元素个数为 n，则所有的排列形式共有 n! 种。每一个元素都可以充当界点，所以充当界点的情况共计有 n 种。故平均时间复杂性 T 应为： T (n) = cn + ∑ [ T (k-1) + T (n-k) ] / n 设：T (0) = T (1) = b T(n) = cn + 2∑ T (i) / n nT (n) = cn2 + 2∑ T (i) (n-1)T (n-1) = c(n-1)2 + 2∑ T (i) 上二式相减的结果为： nT (n) - (n-1)T (n-1) = c(2n-1) + 2T (n-1) nT (n) = c(2n-1) + (n+1) T (n-1)

56 快速排序(Quick Sort) 时间复杂性分析:
所以： T (n) / ( n + 1) = c(2n-1) /( n(n+1)) + T (n-1) / n T (n) / ( n + 1) < = 2c/(n+1) + T (n-1) / n T (n-1) / n < = 2c/n + T (n-2) / (n-1) T (2) / < = 2c/3 + T (1) / 2 于是： T (n) < = 2c(n+1)ln(n+1) + b(n+1) / 2 注意：这里使用了一个公式： ∑1/k < = ∫1/x dx < ln( n + 1) 结论：快速排序在平均情况下的时间复杂性为 O(nlogn) 阶的，通常认为是在平 均情况下最佳的排序方法。

57 快速排序(Quick Sort) 快速排序的不足和克服方法 1、最坏情况下 时间复杂性为 O(n2) 级。如：在序列已是正序的情况下。
10、20、30、40、50、60、70、80 界点 10 ，共进行 7 次比较。 10、20、30、40、50、60、70、80 界点 20 ，共进行 6 次比较。 10、20、30、40、50、60、70、80 界点 60 ，共进行 2 次比较。 10、20、30、40、50、60、70、80 界点 70 ，共进行 1 次比较。 在最坏情况下：总的比较次数为：(n-1) + (n-2) + … = n2 /2=O(n2) 原因：界点选择不当。改进：随机选取界点或最左、最右、中间三个元素中的值处于中间的作为界点，通常可以避免最坏情况。

58 快速排序(Quick Sort) 快速排序的不足和克服方法
2、在序列差不多排好序时，采用直接插入排序、起泡排序等排序方法。序列的个数通常取为 10 左右。 3、将递归改成非递归算法。避免进出栈、恢复断点等工作。速度加快。

59 10.4 选择排序 选择排序的基本思想是：每一趟在ri到rn共n-i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。 简单选择排序 树形选择排序 堆排序

60 简单选择排序 一趟简单选择排序的操作为： 通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，用来和第i个记录交换。 Void SelectSort( SqList &L){ // 对顺序表L作简单选择排序 for( i=1; i<L.length; i++){ k=i; for( j=i+1; j<=L.length; j++) if( L.r[j].key < l.r[k].key) k = j; if( i!=k) L.r[i] L.r[k]; } } // SelectSort

61 简单选择排序 例： 49 38 65 97 76 13 27 49’ 13 38 65 97 76 49 27 49’ 13 27 65 97 76 49 38 49’ 13 27 38 97 76 49 65 49’ 13 27 38 49 76 97 65 49’ 13 27 38 49 49’ 97 65 76 13 27 38 49 49’ 65 97 76 13 27 38 49 49’ 65 76 97

62 简单选择排序 直接选择排序的时间复杂度： 1、无论初始状态如何，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：n(n-1)/2 2. 当文件为正序时，移动次数为0; 移动次数最大值为3(n-1)。 直接选择排序是不稳定的排序方法。

63 简单选择排序 直接选择排序的时间复杂度： 1、无论初始状态如何，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：n(n-1)/2 2. 当文件为正序时，移动次数为0; 移动次数最大值为3(n-1)，何时取得最大值？ 改进的出发点应是如何减少比较的次数。 直接选择排序是不稳定的排序方法。

64 树形选择排序 树形选择排序(Tree Selection Sort),又称锦标赛排序(Tournament Sort)，是一种按照锦标赛的思想进行选择排序的方法。

65 树形选择排序 例：49，38，65，97，76，13，27，49 13 选出最小者 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49

66 树形选择排序 例：49，38，65，97，76，13，27，49 选出次最小者，应利用上次比 较的结果。从被 13 打败的结 点 27、76、38 中加以确定。 27 38 27 38 65 76 27 49 38 65 97 76 ∞ 27 49

67 树形选择排序 时间复杂度为：O(nlog2n) 需要较多的辅助存储。

68 10.4.3 堆排序 堆排序（Heap Sort）只需一个记录大小的辅助存储。
堆的定义： n 个元素的序列 { k1, k2, …, kn-1 }，当且仅当满足以下关系时，称之为堆： ki <= k2i AND ki <= k2i+1 ( i = 0,1,2, … , n/2); 或 ki >= k2i AND ki >= k2i+1 ( i = 0,1,2, … , n/2); 且分别称之为最小化堆(小根堆)和最大化堆(大根堆)。

69 堆排序 例: 序列 { 96,83,27,11,9} 最大化堆 { 12,36,24,85,47,30,53,91} 最小化堆 1 1 96 12 3 2 2 3 83 27 36 24 7 4 5 4 5 6 11 9 85 47 30 53 8 91

70 堆排序 堆排序： 在排序过程中，将序列看成是一棵完全二叉树的顺序存储，先建立一个大根堆（将原序列转换为堆的次序），然后依次将第1个记录与第n、n-1、…、2个记录互换，每次互换完成后重新调整使其前面的部分仍为堆。 可见，堆排序的两个关键问题是： 　　1）如何将一个无序序列调整为堆？ 　　2）如何在互换堆顶之后重新调整为堆？ 大根堆 排好序的部分

71 堆排序 1）如何将一个无序序列调整为堆？ 堆排序的第一个工作是建堆，即把整个记录序列调整为一个堆。显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i >n/2的结点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序号为n/2，n/2-1，...，1的结点作为根的子树都调整为堆即可。自下而上 我们以大根堆为例进行说明

72 10.4.3 堆排序 2）如何在互换堆顶之后重新调整为堆？ 若已知结点i的左右子树已是堆，如何将以i为根的完全二叉树也调整为堆？
解决这一问题可采用“筛选法”，其基本思想是：因为i的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在i和它的左右孩子中选取关键字最大的结点放到i的位置上。 若i的关键字已是三者中的最大者，则无须做任何调整，以i为根的子树已构成堆， 否则必须将i和具有最大关键字的左孩子2i或右孩子2i+1进行交换。假定2i的关键字最大，将i和2i交换位置，交换之后有可能导致2i为根的子树不再是堆，但由于2i的左右子树仍然是堆，于是可以重复上述过程，将以2i为根的子树调整为堆，...，如此逐层递推下去，最多可能调整到树叶。自上而下

73 堆排序 例： 49，38，65，97，76，13，27，49 ? 38 49 13 27 65 76 97

74 Step 0 先将其看作树 49，38，65，97，76，13，27，49 49 38 65 97 76 13 27 49

75 Step 1 树叶已经满足堆条件 49，38，65，97，76，13，27，49 49 38 65 97 76 13 27 49

76 Step 2 添加97，仍满足 49，38，65，97，76，13，27，49 49 38 65 97 76 13 27 49

77 Step 3 添加65，仍满足 49，38，65，97，76，13，27，49 49 38 65 97 76 13 27 49

78 Step 4 添加38，不满足 49，38，65，97，76，13，27，49 49 38 65 97 76 13 27 49

79 Step 5 与较大子节点97交换 49，97，65，38，76，13，27，49 49 97 65 38 76 13 27 49

80 Step 6 与较大子节点49交换 49，97，65，49，76，13，27，38 49 97 65 49 76 13 27 38

81 Step 7 添加49，破坏堆条件 49，97，65，49，76，13，27，38 49 97 65 49 76 13 27 38

82 Step 8 交换49与97 97，49，65，49，76，13，27，38 97 49 65 49 76 13 27 38

83 Step 9 交换49与76 97，76，65，49，49，13，27，38 97 76 65 49 49 13 27 38

84 树的表示不是必要的 49，38，65，97，76，13，27，49 49，97，65，38，76，13，27，49
49，97，65，49，76，13，27，38 97，49，65，49，76，13，27，38 97，76，65，49，49，13，27，38

85 10.4.3 堆排序 算法实现： void HeapAdjust (SqList &H, int s, int m) {
　　// 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义， 　　// 本函数依据关键字的大小对H.r[s]进行调整，使H.r[s..m]成为一 　　// 个大顶堆（对其中记录的关键字而言） 　　H.r[0] = H.r[s];　　　　　　　// 暂存根结点的记录 　　for ( j=2*s; j<=m; j*=2 ) { 　// 沿关键字较大的孩子结点向下筛选 　　　if ( j<m && H.r[j].key<H.r[j+1].key ) 　　　　++j; 　　　　　　　　　　　// j 为关键字较大的孩子记录的下标 　　　if ( H.r[0].key >= H.r[j].key ) break; // 不需要调整，跳出循环 　　　H.r[s] = H.r[j]; s = j; 　　　// 将大关键字记录往上调 　　}// for 　　H.r[s] = H.r[0]; 　　　　　　　// 回移筛选下来的记录 　} // HeapAdjust

86 堆排序 上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区r[1]到r[n]建成一个大根堆，可用以下语句实现： for (i = n/2; i>0; i--) HeapAdjust (H, i, H.length);

87 堆排序 由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将r[1]和r[n]交换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区r[1]到r[n-1]调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用HeapAdjust函数将r[1]到r[n-1]调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录r[n-1]交换，如此反复进行下去。

88 10.4.3 堆排序 堆排序算法: void HeapSort ( SqList &H ) { // 对顺序表H进行堆排序
　　for ( i=H.length/2; i>0; --i ) 　// 将 H.r[1..H.length] 建成大顶堆 　　　HeapAdjust ( H, i, H.length ); 　　H.r[1] ←→ H.r[H.length]; 　　　// 互换"堆顶"和"堆底"的记录 　　for ( i=H.length-1; i>1; --i ) { 　　　HeapAdjust(H, 1, i); // 从根开始调整，将 H.r[1..i] 重新调整为大顶堆 　　　H.r[1] ←→ H.r[i]; 　　　　　　// 互换"堆顶"和当前的"堆底"，使已有序的记录沉积在底部 　　}//for } // HeapSort

89 10.4.3 堆排序 堆排序的时间复杂度 堆排序的时间复杂性为O(n log2n)
对深度为k的堆，HeapAdjust中关键字比较次数至多为2(k-1), ……… 堆排序是不稳定的排序方法。 堆排序在最坏的情况下，其时间复杂度也为O(nLogn)，这一点相对于快速排序而言是最大的优点。

90 10.5 归并排序 归并排序的基本操作是将两个或两个以上的有序记录序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过“逐趟归并”使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。 2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列。这个操作对顺序表而言是极其容易实现的，只要依关键字从小到大进行“复制”即可。

91 10.5 归并排序 将两个有序表合并到另一个有序表的过程：
设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键字小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。

92 10.5 归并排序 例(2-路归并排序的示例)： 49, 38, 65, 97, 76, 13, 27, 49 (38, 49), (65, 97), (13, 76), (27, 49) (38, 49, 65, 97), (13, 27, 49, 76) 13, 27, 38, 49, 49, 65, 76, 97

93 10.5 归并排序 将两个相邻的有序子序列“归并”为一个有序序列的算法
void Merge (RcdType SR[], RcdType 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++]; 　　} // 将剩余的 SR[i..m] 复制到TR 　　while (i<=m) TR[k++] = SR[i++]; // 将剩余的 SR[j..n] 复制到TR 　　while (j<=n) TR[k++] = SR[j++]; 　 } // Merge

94 10.5 归并排序 递归形式的2-路归并排序算法： void Msort ( RcdType SR[], RcdType TR1[], int s, int t ) 　{ 　　// 对SR[s..t]进行归并排序，排序后的记录存入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] 　　} // else } // Msort void MergeSort (SqList &L) 　{ 　　// 对顺序表L作2-路归并排序 　　MSort(L.r, L.r, 1, L.length); } // MergeSort

95 10.5 归并排序 容易看出，2-路归并排序的时间复杂度为 O (nlogn)。
对一个长度为 n 的记录序列需进行log2n趟的归并，而每一趟需进行关键字比较和记录移动的时间列和 n 成正比。 归并排序是稳定的排序方法。 不足的是它需要的辅助存储为O(n)

96 10.6 基数排序 基数排序(Radix Sorting)不需要进行记录关键字间的比较。
基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。 多关键字的排序 链式基数排序

97 10.6.1 多关键字的排序 多关键字排序方法示例： 如对扑克牌的排序 每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。
对以上排序，可以先对花色排序，或先对面值排序。

98 多关键字的排序 多关键字有序的概念 考虑序列{V1,..., Vn}，每个对象Vi含d个关键字(Ki1,Ki2,..., Kid)。若对序列中的任意两个记录Vi和Vj(i<j)都有 (Ki1,Ki2,..., Kid) < (Kj1,Kj2,..., Kjd) 则称序列对关键字(Ki1,Ki2,..., Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。

99 10.6.1 多关键字的排序 多关键字排序 原理：根据组成关键字的各位的值进行排序。 实现基数排序的两种方法：
1 最高位优先(MSD)排序：从关键 字的高位到低位 2 最低位优先(LSD)排序：从关键字 的低位到高位 MSD方法通常是一个递归的过程。

100 10.6.1 多关键字的排序 多关键字排序 LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：
(Ki1,Ki2,..., Kid) 如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。 MSD方法按K1,K2,K3的顺序对所有对象排序； LSD方法按K3,K2, K1的顺序对所有对象排序。

101 10.6.2 链式基数排序 基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键字进行排序。
此时可将单关键字K看成是一个子关键字组： (Ki1,Ki2,..., Kid) 排序过程：设关键字共有d位，让j= d, d-1,...,1, 依次执行d次“分配”与“收集”。

102 链式基数排序 例： 49, 38, 65, 97, 76, 13, 27, 49 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 分配 13, 65,76,97 38, 49 27, 13,65,76,27,97,38,49,49 收集 13,27,38,49, ,76, 49 13, 27, 38, 49, 49, 65, 76, 97 收集

103 10.6.2 链式基数排序 在描述基数排序的算法之前，尚需重新定义记录和顺序表类型： const MAX_NUM_OF_KEY = 8;
　　　　　// 关键字项数的最大值，暂定为8 　const RADIX = 10; 　　　　　// 关键字基数，此为十进制整数的基数 　typedef struct { 　　KeysType keys[MAX_NUM_OF_KEY]; // 关键字 　　InfoType otheritems; // 其它数据项 　} RcdType; // 基数排序中的记录类型 　　RcdType r[MAXSIZE+1]; 　　int length; 　// 顺序表长度 　　int bitsnum;　// 关键字位数 　} SqList;　　　 // 顺序表类型

104 10.6.2 链式基数排序 void LRadixSort(SqList &L) {
　　int Next[L.length+1]; 　　for (i=0; i<L.length; ++i) Next[i] = i+1; 　　Next[L.length] = 0;　　　　// 将L视作静态(循环)链表 　 // 按最低位优先依次对各关键字进行分配和收集 　　for ( k=L.bitsnum-1; k>=0; --k) { 　　　Distribute(L.r, k, f, e, Next);　// 第 k 趟分配 　　　Collect(L.r, k, f, e, Next); 　　// 第 k 趟收集 　　}// for 　　Arrange(L, Next); 　　// 按 Next[] 的值调整 L 中的记录 　} // LRadixSort

105 10.6.2 链式基数排序 void Distribute (RcdType R[], int k, int f[], int e[]) {
　// R中记录已按(R.keys[k+1],...,R.keys[L.bitsnum-1])有序 　//本算法按R.keys[k]建立RADIX个子表，使同一子表中记录的 　// keys[k]相同。f[0..RADIX-1]和e[0..RADIX-1]分别指向各 　// 子表中第一个和最后一个记录 　　for (j=0; j<Radix; ++j) f[j] = 0; 　// 各子表初始化为空表 　　for (p=Next[0]; p; p=Next[p]) { 　　　// ord 将记录中的关键字keys[k]映射到[0..RADIX-1]中 　　　j = ord(R[p].keys[k]); 　　　if ( !f[j] ) f[j] = p; 　　　else Next[e[j]] = p; 　　　e[j] = p; 　　　　　　　// 将 p 所指的结点插入相应子表 　　}// for } // Distribute

106 10.6.2 链式基数排序 void Collect (RcdType R[], int k, int f, int e) {
　//本算法按R.keys[k]自小至大地将 f[0..RADIX-1] 所指各子表 　// 依次链接成一个链表，e[0..RADIX-1] 为各子表的尾指针 　 // 找第一个非空子表，succ 为求后继函数 for ( j=0; !f[j]; j=succ(j)); // Next[0]指向第一个非空子表中第一个结点 Next[0] = f[j]; t = e[j]; while ( j<RADIX ) { // 找下一个非空子表 　　　for (j=succ(j); j<RADIX-1 && !f[j]; j=succ(j) ); // 链接两个非空子表 　　　if ( f[j] ) { r[t].next = f[j]; t = e[j]; } 　　}// while 　　Next[t] = 0;　// t 指向最后一个非空子表中的最后一个结点 } // Collect

107 链式基数排序 分析链式基数排序的时间复杂度： 假设 n 为记录个数，rd 为基数值，d 为构成逻辑关键字的关键字位数。 由于每一趟的“分配”都是对全部记录处理一遍，因此它的时间复杂度是O (n)， 而每一趟的“收集”只是巡查一遍队列，依次将各非空队列的队尾指针所指结点链接到下一个非空队列的队头指针所指结点，因此它的时间复杂度是O (rd)， 因此一趟分配和收集的时间复杂度为O (n+rd)， 对每一位关键字进行一趟分配和收集，因此总的时间复杂度为O (d(n+rd))， 一般情况下，相比 n 而言，rd 要小得多，因此可简写为O (dn)。 换句话说，当待排序序列中的记录数量很大，而逻辑关键字的"位数"较小，此时用基数排序法进行排序将比快速排序的效率更高。

108 10.7 各种内部排序方法的比较讨论 选取排序方法时需要考虑的因素有： 待排序的记录数目 记录本身信息量的大小 关键字的结构及其分布情况
对排序稳定性的要求 语言工具的条件、辅助空间的大小

109 10.7 各种内部排序方法的比较讨论 一、 时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O (nlogn) 的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在 n 值较大的情况下，归并排序较堆排序更快； 时间复杂度为O (n2) 的有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少； 时间复杂度为O (n) 的排序方法只有基数排序一种。

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

111 10.7 各种内部排序方法的比较讨论 一、 时间性能 4. 以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过程中占的比例更大，从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。

112 10.7 各种内部排序方法的比较讨论 二、空间性能 指的是排序过程中所需的辅助空间大小。
　1. 所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O (1)。 　2. 快速排序为O (logn)，为递归程序执行过程中栈所需的辅助空间。 　3. 归并排序和基数排序所需辅助空间最多，其空间复杂度为O (n)。

113 10.7 各种内部排序方法的比较讨论 三、排序方法的稳定性能
　1. 稳定的排序方法指的是，对于两个关键字相等的记录在经过排序之后，不改变它们在排序之前在序列中的相对位置。 　2. 除希尔排序、快速排序和堆排序是不稳定的排序方法外，本章讨论的其它排序方法都是稳定的（前面给出的简单选择排序算法也是不稳定的）。 　3. "稳定性"是由方法本身决定的。一般来说，排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。如本章10.4.1节中的选择排序算法没有满足"稳定"的要求是因为，每趟在右部无序区找到最小记录后常要跳过很多记录进行交换调整。显然若"交换调整"的方式改一改就能写出稳定的选择排序算法。而对不稳定的排序方法，不论其算法的描述形式如何，总能举出一个说明它不稳定的实例来。

114 10.7 各种内部排序方法的比较讨论 几种排序方法的比较： 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入排序
O(n2) O(n) O(1) Y 起泡排序 简单选择排序 快速排序 O(nlogn) O(logn) N 堆排序 2-路归并排序 基数排序 O(dn)

115 课后习题 Project ID: 13 编写实现以下排序算法的程序，观察排序所需平均时间（依赖长度）： 请尽量实现各种时间复杂性O(n Log n)或相当的算法。 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序 交换排序 起泡排序 快速排序 选择 简单选择 堆排序 归并 基数

116 THE END OF THIS LECTURE