第九章 排序 课前导学 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序 9.4 选择类排序 9.5 归并排序

Presentation on theme: "第九章 排序 课前导学 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序 9.4 选择类排序 9.5 归并排序"— Presentation transcript:

1 第九章 排序 课前导学 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序 9.4 选择类排序 9.5 归并排序
9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序 9.4 选择类排序 9.5 归并排序 9.6 分配类排序 9.7 各种内部排序方法的比较讨论 9.8 总结与提高

2 【学习目标】 1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。
2．掌握各种排序方法的时间复杂度的分析方法。　　3．理解排序方法“稳定”或“不稳定”的含义。 ** 了解各种排序方法实现时所依据的原则以及它们的主要操作（“关键字间的比较”和“记录的移动”）的时间分析。

3 【重点和难点】 掌握希尔排序、快速排序、堆排序和归并排序等几种高效方法。
　掌握希尔排序、快速排序、堆排序和归并排序等几种高效方法。 【知识点】 　　排序、直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序，排序方法的综合比较

4 9.1 排序的基本概念 排序 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列的过程叫排序。

5 2. 排序的基本操作 3. 排序方法的稳定性 比较两个关键字大小 （必须的） 将记录从一个位置移动到另一个位置（可以设法避免）
2. 排序的基本操作 比较两个关键字大小 （必须的） 将记录从一个位置移动到另一个位置（可以设法避免） 3. 排序方法的稳定性 假设Ki=Kj , i≠j，在排序前的序列中Ri领先于Rj，若排序后Ri仍领先于Rj，则称该排序方法是稳定的，否则就是不稳定的。 注意：待排序的记录序列可以用顺序表表示，也可以用链表表示。本章讨论的排序算法一律以顺序表为操作对象。

6 4. 内部排序和外部排序 内部排序： 整个排序过程完全在内存中进行的排序 外部排序：
4. 内部排序和外部排序 内部排序： 整个排序过程完全在内存中进行的排序 外部排序： 由于待排序数据量太大，内存无法完全容纳所有数据，需要借助外部存储设备才能完成的排序。

7 5. 排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则
插入类排序：直接插入排序、折半插入排序、希尔排序 交换类排序：冒泡排序、快速排序 选择类排序：简单选择排序、树形选择排序（锦标赛排序） 、堆排序 归并排序：2-路归并排序 分配类排序：多关键字排序、链式基数排序 按排序所需工作量 简单的排序方法：T(n)=O(n²) 先进的排序方法：T(n)=O(nlogn) 分配类排序：T(n)=O(d.n)

8 9.2 插入类排序 插入排序的基本思想： 是在一个有序序列中插入一个新的记录 方法： 直接插入排序 折半插入排序 希尔排序

9 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。 一趟直接插入排序思想：在对记录序列R[1..n]的排序过程中，区段R[1..i-1]中的记录已按关键字非递减的顺序排列，将 R[i] 插入到有序序列 R[1..i-1] 中，使区段 R[1..i] 中的记录按关键字非递减顺序排列。 动画演示

10 实现一趟插入排序的步骤： 1) 在 R[1..i-1] 中查找 R[i] 的插入位置，即确定j(0≤j＜i)使得 　　　　R[1..j].key≤R[i].key＜R[j+1..i-1].key 2) 将 R[j+1..i-1] 中的记录后移一个位置； 3) 将 R[i] 插入到 j+1 的位置。

11 例 i= ( ) i= ( ) i= ( ) i= ( ) i= ( ) i= ( ) i= ( ) 49 i= ( ) 49 49 27 49 65 76 97） ( ) 排序结果：

12 排序算法： void InsSort(RecordType r[], int length)
/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/ { int i,j; for (i=2; i<=length; i++) r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/ j=i-1; while (r[0].key< r[j].key ) /* 寻找插入位置 */ r[j+1]= r[j]; j=j-1; } r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ } /* InsSort */

13 直接插入排序是稳定排序 先复制哨兵再比较时: 算法评价 （1）时间复杂度： 若待排序记录按关键字从小到大排列(正序) 关键字比较次数：
记录移动次数： 先复制哨兵再比较时: 若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 记录移动次数： 若待排序记录是随机的，取平均值 关键字比较次数： 记录移动次数： T(n)=O(n²) （2）空间复杂度：S(n)=O(1)

14 - 折半插入排序 排序过程：用折半查找方法确定插入位置的排序叫~ 例 i=1 (30) 13 70 85 39 42 6 20
…... i= ( ) 20 i= ( ) 20 s j m i= ( ) 20 s j m i= ( ) 20 s j m i= ( ) 20 s j i= ( )

15 void BinSort (RecordType r[], int length)
/*对记录数组r进行折半插入排序，length为数组的长度*/ { int i,j; RecordType x; int low,high,mid; for ( i=2; i<=length ; ++i ) x= r[i]; low=1; high=i-1; while (low<=high ) /* 确定插入位置*/ mid=(low+high) / 2; if ( x.key< r[mid].key ) high=mid-1; else low=mid+1; } for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j]; /* 记录依次向后移动 */ r[low]=x; /* 插入记录 */ }/*BinSort*/

16 算法评价: （1）时间复杂度： 折半插入仅减少了关键字比较次数: O(log2n), 记录移动次数不变，所以时间复杂度：T(n)=O(n²)
（2）空间复杂度：S(n)=O(1) 折半插入排序是稳定排序

17 - 希尔排序(缩小增量法) 排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。 实验研究表明,当增量序列dl选取合适时,其时间复杂度为O(n3/2)

18 例 初始： 取d1=5 一趟分组： 一趟排序： 取d2=3 二趟分组： 二趟排序： 取d3=1 三趟分组： 三趟排序：

19 void ShellInsert(RecordType r[], int length, int delta)
/*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/ { int i,j; for(i=1+delta;i<= length; i++) /* 1+delta为第一个子序列的第二个元素的下标 */ if(r[i].key < r[i-delta].key) { r[0]= r[i]; /* 备份r[i] (不做监视哨) */ for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta) r[j+delta]= r[j]; r[j+delta]= r[0]; } }/*ShellInsert*/

20 void ShellSort(RecordType r[], int length, int delt[], int n)
/*对记录数组r做希尔排序，length为数组r的长度，delta 为增量数组，n为delta[]的长度 */ { int i; for(i=0 ; i<=n-1; ++i) ShellInsert(r, length, delt[i]); }

21 希尔排序特点： 子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列； 希尔排序可提高排序速度，因为
分组后n值减小，n²更小，而T(n)=O(n²), 所以T(n)从总体上看是减小了 关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序 增量序列取法 无除1以外的公因子 最后一个增量值必须为1 希尔排序是一种不稳定的排序方法

22 9.3 交换类排序 交换排序的基本思想： 利用交换元素的位置进行排序。 方法： 冒泡排序 快速排序 （一种分区交换排序方法）

23 1. 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止

24 void BubbleSort(RecordType r[], int length )
/*对记录数组r做冒泡排序，length为数组的长度*/ { int n,i,j; nt change; RecordType x; n=length; change=TRUE; for ( i=1 ; i<= n-1 && change ;++i ) { change=FALSE; for ( j=1 ; j<= n-i ; ++j) if (r[j].key > r[j+1].key ) { x= r[j]; r[j]= r[j+1]; r[j+1]= x; change=TRUE; } } /* BubbleSort

25 算法评价 T(n)=O(n²) (1) 时间复杂度: 最好情况（正序） 比较次数：n-1 移动次数：0 最坏情况（逆序） 比较次数：
(2) 空间复杂度：S(n)=O(1) 冒泡排序是稳定排序

26 2. 快速排序 基本思想： 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

27 排序过程： 对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止

28 从右边找小于X的，从左边找大于X的，进行交换，直到走到一起。
例 初始关键字： 27 13 49 49 49 97 65 49 i j j i i j i j i j j i i j i j 完成一趟排序： ( ) ( ) 分别进行快速排序： ( 13) (38) ( ) (97) 快速排序结束： 从右边找小于X的，从左边找大于X的，进行交换，直到走到一起。

29 快速排序算法 void QKSort(RecordType r[],int low, int high )
/*对记录数组r[low..high]用快速排序算法进行排序*/ { int pos; if(low<high) pos=QKPass(r, low, high); /*调用一趟快速排序，将枢轴元素为界划分两个子表*/ QKSort(r, low, pos-1); /*对左部子表快速排序*/ QKSort(r, pos+1, high); /*对右部子表快速排序*/ }

30 int QKPass(RecordType r[],int left,int right)
/*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/ { RecordType x; int low,high; x= r[left]; /* 选择基准记录*/ low=left; high=right; while ( low<high ) while (low< high && r[high].key>=x.key ) /* high从右到左找小于x.key的记录 */ high--; if ( low <high ) {r[low]= r[high]; low++;} /* 找到小于x.key的记录，则进行交换*/ while (low<high && r[low].key<x.key ) /* low从左到右找大于x.key的记录 */ low++; if ( low<high ){ r[high]= r[low]; high--; } /* 找到大于x.key的记录，则交换*/ } r[low]=x; /*将基准记录保存到low=high的位置*/ return low; /*返回基准记录的位置*/ } /* QKPass */

31 严蔚敏书上的算法描述 int Partition (SqList &L,int low,int high){
//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。 L.r[0]=L.r[low]; //用子表的第一个记录作枢轴记录 pivotkey =L.r[low].key; //枢轴记录关键字 while (low<high){ //从表的两端交替地向中间扫描 while (low<high &&L.r[high].key>=pivotkey) --high; L.r[low] =L.r[high]; //将比枢轴记录小的记录移到低端 while (low<high &&L.r[low].key>=pivotkey) ++ low; L.r[low] =L.r[high]; //将比枢轴记录大的记录移到高端 } L．r[low]=L.r[0]; //枢轴记录到位 return low; //返回枢轴位置 }//Partition

32 （1）时间复杂度 T(n)=O(nlogn)
算法评价 （1）时间复杂度 T(n)=O(nlogn) 最好情况（每次总是选到中间值作枢轴） T(n)=O(nlogn) 最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²) 快速排序不适于对原本有序或基本有序的记录序列进行排序。 （2）空间复杂度：需栈空间以实现递归 最坏情况：S(n)=O(n) 一般情况：S(n)=O(logn) 就平均时间而言，快速排序是目前被认为最好的一种内部排序方法，但是不稳定的排序。

33 9.4 选择类排序 选择排序的基本思想： 每次从待排序的数据元素集合中选择最小（或最大）的数据元素放到数据元素集合的最前面（或最后面），当数据元素集合为空时排序结束。 方法： 简单选择排序 堆排序 树形选择排序（锦标赛排序）

34 1. 简单选择排序 基本思想：在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。 排序过程：
首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束

35 k k k 例 i=1 初始： [ ] 13 49 j j j j j j k k i=2 一趟： [ ] 27 38 j j j j j 二趟： [ ] 三趟： [ ] 四趟： [ ] 五趟： [ ] 六趟： [97 ] 排序结束：

36 算法描述 void SelectSort(RecordType r[], int length)
/*对记录数组r做简单选择排序，length为数组的长度*/ { int i,j,k; int n; RecordType x; n=length; for ( i=1 ; i<= n-1; ++i) k=i; for ( j=i+1 ; j<= n ; ++j) if (r[j].key < r[k].key ) k=j; if ( k!=i) x= r[i]; r[i]= r[k]; r[k]=x; } } /* SelectSort */

37 算法评价 （1）时间复杂度 T(n)=O(n²) （2）空间复杂度：S(n)=O(1) 记录移动次数 最好情况：0 最坏情况：3(n-1)
比较次数： T(n)=O(n²) （2）空间复杂度：S(n)=O(1) 简单选择排序是一种不稳定的排序方法

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

39 Winner ∞ 08 21 63 25* 25 49 16 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 如果 n 不是 2 的 k 次幂，则让叶结点数补足到满足 2k-1 < n  2k 的 2k 个。叶结点上面一层的非叶结点是叶结点排序码两两比较的结果。最顶层是树的根。 在图例中, 最下面是对象排列的初始状态,相当于一棵满全二叉树的叶结点, 它存放的是所有参加排序的对象的排序码。

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

41 a[0] up 对手不参选 Winner (胜者) 08 21 08 21 08 63 21 25 49 25* 16 08 63
VS. 比较 Winner (胜者) 08 a[0] VS. 21 08 VS. VS. 21 25* 08 63 up VS. VS. VS. 21 25 49 25* 16 08 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 形成初始胜者树（最小排序码上升到根） 排序码比较次数 : 6

42 a[1] 输出冠军并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 16 21 16 21 16 63 21 25 49
VS. 比较 Winner (胜者) 16 a[1] VS. 21 16 VS. 21 25* 16 63 up 21 25 49 25* 16 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出冠军并调整胜者树后树的状态 排序码比较次数 : 2

43 a[2] 输出亚军并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 21 21 63 21 63 21 25 49 25*
VS. 比较 Winner (胜者) 21 a[2] VS. 21 63 up 21 25* 63 21 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出亚军并调整胜者树后树的状态 排序码比较次数 : 1

44 a[3] 输出第三名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 25 25 63 25 63 25 49 25* 63
VS. 比较 Winner (胜者) 25 a[3] VS. 25 63 VS. 25 25* 63 up 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第三名并调整胜者树后树的状态 排序码比较次数 : 2

45 a[4] 输出第四名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 63 63 49 25* 63 排序码比较次数 : 1
VS. 比较 Winner (胜者) 25* a[4] VS. 25* 63 up 25* 63 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第四名并调整胜者树后树的状态 排序码比较次数 : 1

46 a[5] 输出第五名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 63 63 49 63 排序码比较次数 : 1
VS. 比较 Winner (胜者) 49 a[5] VS. 49 63 up 49 63 up 49 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第五名并调整胜者树后树的状态 排序码比较次数 : 1

47 a[6] 全部比赛结果输出时树的状态 up 对手不参选 Winner (胜者) 63 63 63 63 排序码比较次数 : 0 VS. 比较
tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 全部比赛结果输出时树的状态 排序码比较次数 : 0

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

49 3. 堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆。 小顶堆 大顶堆
或 (i=1,2,…...n/2) Ki  k2i Ki  k2i+1 Ki  k2i Ki  k2i+1 例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97） 13 27 38 49 65 76 50 97 小顶堆 大顶堆 96 27 9 11 38 83 可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值

50 堆排序： 将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？

51 先讨论第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”

52 例：调整堆 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 13 27 38 49 65 76 50 97 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：

53 49 65 50 27 38 76 97 13 输出： 76 65 50 27 38 49 97 13 输出： 50 65 76 27 38 49 97 13 输出： 97 65 76 27 38 49 50 13 输出： 65 97 76 27 38 49 50 13 输出： 97 65 76 27 38 49 50 13 输出：

54 76 65 97 27 38 49 50 13 输出： 97 65 76 27 38 49 50 13 输出： 97 65 76 27 38 49 50 13 输出：

55 第一个问题解决方法 从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。

56 建立一个堆的过程 例 含8个元素的无序序列（49，38，65，97，76，13，27，50） 49 65 38 27 13 76 50 97
例 含8个元素的无序序列（49，38，65，97，76，13，27，50） 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 65 38 27 13 76 97 50 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97

57 建立初堆算法 void crt_heap(RecordType r[], int length ) /*对记录数组r建堆，length为数组的长度*/ { int i,n; n= length; for ( i=n/2; i >= 1; --i) /* 自第[n/2]个记录开始进行筛选建堆 */ sift(r,i,n); }

58 调整堆的算法 void sift(RecordType r[], int k, int m)
/* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */ { RecordType t; int i,j; int x; int finished; t= r[k]; /* 暂存"根"记录r[k] */ x=r[k].key; i=k; j=2*i; finished=FALSE; while( j<=m && !finished ) { if (j<m && r[j].key< r[j+1].key ) j=j+1; /* 若存在右子树， 且右子树 根的关键字大，则沿右分支"筛选" */ if ( x>= r[j].key) finished=TRUE; /* 筛选完毕 */ else { r[i] = r[j]; i=j; j=2*i; } /* 继续筛选 */ } r[i] =t; /* r[k]填入到恰当的位置 */

59 堆排序完整算法 void HeapSort(RecordType r[],int length)
/* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */ { int i,n; RecordType b; crt_heap(r, length); n= length; for ( i=n ; i>= 2; --i) b=r[1]; /* 将堆顶记录和堆中的最后一个记录互换 */ r[1]= r[i]; r[i]=b; sift(r,1,i-1); /* 进行调整，使r[1..i-1]变成堆 */ } } /* HeapSort */

60 算法评价： T(n)=O(nlogn) 时间复杂度： 最坏情况下T(n)=O(nlogn) 空间复杂度：S(n)=O(1)
堆排序是不稳定的排序，不适合记录个数n较少的情况，对于n较大的情况很有效。

61 9.5 归并排序 2-路归并排序： 归并——将两个或两个以上的有序表组合成一个新的有序表。 排序过程
9.5 归并排序 归并——将两个或两个以上的有序表组合成一个新的有序表。 2-路归并排序： 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到n/2个长度为2或1的有序子序列 再两两合并，……如此重复，直至得到一个长度为n的有序序列为止

62 例 初始关键字： [49] [38] [65] [97] [76] [13] [27] 一趟归并后： [ ] [ ] [ ] [27] 二趟归并后： [ ] [ ] 三趟归并后： [ ]

63 相邻两个有序子序列的合并算法 while ( (i<=mid) && (j<=high) )
void Merge (RecordType r1[], int low, int mid, int high, RecordType r2[]) /* 已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low..high] */ { int i,j,k; i=low; j=mid+1; k=low; while ( (i<=mid) && (j<=high) ) if ( r1[i].key<=r1[j].key ) { r2[k]=r1[i]; ++i;} else { r2[k]=r1[j]; ++j;} ++k; } while( i<=mid ) { r2[k]=r1[i]; k++; i++; } /*剩余部分*/ while( j<=high) { r2[k]=r1[j]; k++; j++; } /*剩余部分*/ } /* Merge */

64 二路归并排序的递归算法 if ( low==high ) r3[low]=r1[low]; else mid=(low+high)/2;
void MergeSort ( RecordType r[], int n ) /* 对记录数组r[1..n]做归并排序 */ { MSort ( r, 1, n, r ); } void MSort(RecordType r1[], int low, int high, RecordType r3[]) /* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */ int mid; RecordType r2[20]; if ( low==high ) r3[low]=r1[low]; else mid=(low+high)/2; MSort(r1,low, mid, r2); MSort(r1,mid+1,high, r2); Merge (r2,low,mid,high, r3); } /* MSort */

65 算法评价 时间复杂度：T(n)=O(nlog2n) 空间复杂度：S(n)=O(n)
归并排序是稳定排序，由于要求附加空间较大，很少用二路归并排序进行内部排序，主要用于外部排序。

66 9.6 分配类排序（也称基数类排序） 基数排序：是一种借助“多关键字排序”的思想来实现“单逻辑关键字排序”的内部排序算法，包括“分配”和“收集”两步操作。 例 对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（ <<< ） 面值（2<3<……<A） 并且“花色”地位高于“面值”

67 1. 多关键字排序方法 最高位优先法（MSD，Most Significant Digit first)：
先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列 最低位优先法(LSD, Least Significant Digit first)： 从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列 动画1 动画2

68 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。

69 2. 链式基数排序 链式基数排序：用链表作存储结构的基数排序 链式基数排序步骤
设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列

70 例 初始状态： 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 083 184 505 008 269 589 063 278 109 930 063 083 184 505 278 008 109 589 269 一趟收集：

71 930 063 083 184 505 278 008 109 589 269 一趟收集： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 109 930 269 589 278 008 184 505 063 083 505 008 109 930 063 269 278 083 184 589 二趟收集：

72 505 008 109 930 063 269 278 083 184 589 二趟收集： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 083 184 278 589 930 063 008 109 269 505 008 063 083 109 184 269 278 505 589 930 三趟收集：

73 f[0]=0 e[0]=0 f[1]=0 e[1]=0 f[2]=0 e[2]=0 f[3]=0 e[3]=0 f[4]=0 e[4]=0
初始状态： 1 278 109 063 930 589 184 505 269 008 083 2 3 4 5 6 7 8 9 10 f[0]= e[0]=0 f[1]= e[1]=0 f[2]= e[2]=0 f[3]= e[3]=0 f[4]= e[4]=0 f[5]= e[5]=0 f[6]= e[6]=0 f[7]= e[7]=0 f[8]= e[8]=0 f[9]= e[9]=0 4 4 3 10 3 6 6 7 7 1 9 1 4 930 063 083 184 505 278 008 109 589 269 3 10 6 7 1 9 2 5 8 2 5 8 2

74 f[0]=0 e[0]=0 f[1]=0 e[1]=0 f[2]=0 e[2]=0 f[3]=0 e[3]=0 f[4]=0 e[4]=0
930 063 083 184 505 278 008 109 589 269 3 10 6 7 1 9 2 5 8 一趟收集： f[0]= e[0]=0 f[1]= e[1]=0 f[2]= e[2]=0 f[3]= e[3]=0 f[4]= e[4]=0 f[5]= e[5]=0 f[6]= e[6]=0 f[7]= e[7]=0 f[8]= e[8]=0 f[9]= e[9]=0 7 2 9 7 4 4 3 8 3 1 1 10 10 5 6 7 505 008 109 930 063 269 278 083 184 589 9 2 4 3 8 1 10 6 5 二趟收集：

75 f[0]=0 e[0]=0 f[1]=0 e[1]=0 f[2]=0 e[2]=0 f[3]=0 e[3]=0 f[4]=0 e[4]=0
7 505 008 109 930 063 269 278 083 184 589 9 2 4 3 8 1 10 6 5 二趟收集： f[0]= e[0]=0 f[1]= e[1]=0 f[2]= e[2]=0 f[3]= e[3]=0 f[4]= e[4]=0 f[5]= e[5]=0 f[6]= e[6]=0 f[7]= e[7]=0 f[8]= e[8]=0 f[9]= e[9]=0 9 10 3 9 2 6 2 8 8 1 7 5 7 9 008 063 083 109 184 269 278 505 589 930 3 10 2 6 8 1 7 5 4 三趟收集： 4 4

76 算法评价 算法描述 时间复杂度： 分配：T(n)=O(n) 收集：T(n)=O(RADIX) 其中：n——记录数 d——关键字数
算法评价 算法描述 时间复杂度： 分配：T(n)=O(n) 收集：T(n)=O(RADIX) T(n)=O(d(n+RADIX)) 简写：O(d·n) 其中：n——记录数 d——关键字数 RADIX——关键字取值范围 空间复杂度： S(n)=2 RADIX个队列指针+n个指针域空间

77 9.7 各种内部排序方法的比较讨论

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

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

80 2. 空间性能 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 快速排序为O(log2n )，为栈所需的辅助空间; 归并排序所需辅助空间最多，其空间复杂度为O(n ); 链式基数排序需附设队列首尾指针，则空间复杂度为O(RADIX )。

81 3. 排序方法的稳定性能 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 对于不稳定的排序方法，只要能举出一个实例说明即可。 快速排序、简单选择排序、希尔排序和堆排序是不稳定的排序方法，其它都是稳定排序。

82 选择排序方法的原则 1) 若待排序的记录个数n值较小（例如n<30），则可选用插入排序法，但若记录所含数据项较多，所占存储量大时，应选用选择排序法。反之，若待排序的记录个数n值较大时，应选用快速排序法。但若待排序记录关键字有"有序"倾向时，就慎用快速排序，而宁可选用堆排序或归并排序，而后两者的最大差别是所需辅助空间不等。

83 2) 快速排序和归并排序在n值较小时的性能不及直接插入排序，因此在实际应用时，可将它们和插入排序"混合"使用。如在快速排序划分子区间的长度小于某值时，转而调用直接插入排序；或者对待排记录序列先逐段进行直接插入排序，然后再利用"归并操作"进行两两归并直至整个序列有序为止。

84 3) 基数排序的时间复杂度为O (d×n)，因此特别适合于待排记录数 n 值很大，而关键字"位数 d "较小的情况。并且还可以调整"基数"（如将基数定为100或1000等）以减少基数排序的趟数d的值。 4) 一般情况下，对单关键字进行排序时，所用的排序方法是否稳定无关紧要。但当按"最次位优先"进行多关键字排序时(除第一趟外)必须选用稳定的排序方法。