第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

本章重点难点 重点：插入排序、快速排序、选择排序、归并排序、基数排序的思想和算法。 难点：堆排序的思想和算法，在实际应用中如何根据实际情况，选择最优的排序算法。

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.1 概述 排序方法的稳定和不稳定 当需要排序的关键字都不相同时,排序的结果是唯一的; 张三 80分 李四 75分 王五 85分 陈六 90分 李四 75分 张三 80分 王五 85分 陈六 90分 陈六 90分 王五 85分 张三 80分 李四 75分

9.1 概述 当排序的关键字中存在相同的情况时,排序方法不唯一; 张三 80分 李四 75分 王五 85分 陈六 80分 李四 75分 张三 80分 陈六 80分 王五 85分 李四 75分 陈六 80分 张三 80分 王五 85分 在排序前后，含相等关键字的记录的相对位置保持不变，称这种排序方法是稳定的； 反之，含相等关键字的记录的相对位置有可能改变，称这种排序方法是不稳定的。

9.1 概述 内部排序和外部排序 在排序过程中，只使用计算机的内存存放待排序记录，称这种排序为内部排序。 排序期间文件的全部记录不能同时存放在计算机的内存中，要借助计算机的外存才能完成排序，称之为“外部排序”。 内外存之间的数据交换次数就成为影响外部排序速度的主要因素。

9.1 概述 存储结构 #define MAXSIZE 1000 // 待排顺序表最大长度 typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RcdType; // 记录类型 typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置 int length; // 顺序表长度 } SqList; // 顺序表类型

9.1 概述 效率分析 (1) 时间复杂度： 关键字的比较次数和记录移动次数。 (2) 空间复杂度： 执行算法所需的附加存储空间。 (3) 稳定算法和不稳定算法

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.2、插入排序 9.2.1 直接插入排序 9.2.2 其他插入排序 9.2.3 希尔排序

9.2.1 直接插入排序 插入排序的思想 (1)一个记录是有序的； (2)从第二个记录开始，将每个记录插入到已排好序的序列中； (3)一直进行到第n个记录。

9.2.1 直接插入排序 算法概述 (1)将序列中的第1个记录看成是一个有序的子序列; (2)从第2个记录起逐个进行插入，直至整个序列变成按关键字有序序列为止； 整个排序过程需要进行比较、后移记录、插入适当位置。从第二个记录到第n个记录共需n-1趟。

9.2.1 直接插入排序 直接插入排序示例演示 49 38 65 38. 76 13 27 38 49 65 38. 76 13 27 38 49 65 38. 76 13 27 38 49 65 38. 76 13 27 65 38 49 38. 76 13 27 38. 38 49 65 76 13 27 38. 38 49 65 76 13 27 38. 38 49 65 76 13 27

9.2.1 直接插入排序 直接插入排序算法 void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; // 复制为监视哨 for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } } // InsertSort

9.2.1 直接插入排序 算法分析 (1)稳定性 直接插入排序是稳定的排序方法。 (2)算法效率 a.时间复杂度 最好情况:比较O(n),移动O(1); 最坏情况:比较O(n2),移动O(n2); 平均O(n2) b.空间复杂度 O(1)。

9.2.2 其它插入排序 折半插入排序思想 (1)在直接插入排序中，r[1..i-1] 是一个按关键字有序的有序序列; (2)可以利用折半查找实现“在r[1..i-1]中查找r[i]的插入位置”; (3)称这种排序为折半插入排序。

9.2.2 其它插入排序 折半插入排序的演示过程 0 1 2 3 4 5 6 7 8 9 10 查22 05 13 19 21 37 56 64 75 80 88 90 low mid= (low+high)/2 high mid high=mid-1 low=mid+1 mid low=mid+1 high=mid-1

9.2.2 其它插入排序 折半插入排序算法 void BiInsertionSort ( SqList &L ) { for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] 在 L.r[1..i-1]中折半查找插入位置； for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } // for } // BInsertSort

9.2.2 其它插入排序 折半插入排序算法 low = 1; high = i-1; while (low<=high) { m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 }

9.2.2 其它插入排序 2路插入排序示例演示 分治的思想 排序49, 38, 65, 97, 76, 13, 27, 49* 例 49 9.2.2 其它插入排序 2路插入排序示例演示 分治的思想 排序49, 38, 65, 97, 76, 13, 27, 49* 例 49 49 38 49 65 38 49 65 97 38 49 65 76 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38

9.2.2 其它插入排序 表插入排序的思想 (1)目的是为了减少在排序过程中进行的 “移动”记录的操作； (2)利用静态链表进行排序，排序中只改为指针； (3)在排序完成之后，一次性地调整各个记录相互之间的位置。

9.2.2 其它插入排序 表插入排序的存储结构 #define SIZE 100 typedef struct { RcdType rc; int next; }SLNode; typedef struct { SLNode r[SIZE]; int length; }SLinkListType;

9.2.2 其它插入排序 表插入排序的示例演示 1 2 3 4 5 6 7 8 初始 状态 key域 next域 M 49 38 65 97 1 2 3 4 5 6 7 8 初始 状态 M 49 38 65 97 76 13 27 49* 1 - key域 next域 M 49 38 65 97 76 13 27 49* 2 1 - M 49 38 65 97 76 13 27 49* 2 3 1 - M 49 38 65 97 76 13 27 49* 2 3 1 4 -

9.2.2 其它插入排序 表插入排序的算法 void LInsertionSort (SLinkListType &SL){ // 对记录序列SL[1..n]作表插入排序 SL.r[0].key = MAXINT ; SL.r[0].next = 1; SL.r[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL.r[0].next;SL.r[k].key<= SL.r[i].key ; j=k, k=SL.r[k].next ) { SL[j].next = i; SL[i].next = k; } // 结点i插入在结点j和结点k之间 }// LinsertionSort

9.2.2 其它插入排序 表插入排序的示例演示 i=1 p=6 q=7 i=2 p=7 q=2 i=3 p=2 q=1 i=4 p=1 1 2 3 4 5 6 7 8 i=1 p=6 q=7 M 49 38 65 97 76 13 27 49* 6 8 1 5 4 7 2 3 i=2 p=7 q=2 M 13 38 65 97 76 49 27 49* 6 (6) 1 5 4 8 2 3 i=3 p=2 q=1 M 13 27 65 97 76 49 38 49* 6 (6) (7) 5 4 8 1 3 i=4 p=1 q=8 M 13 27 38 97 76 49 65 49* 6 (6) (7) 4 8 5 3 p=SL.r[p].next

9.2.2 其它插入排序 表插入排序的记录调整算法 void Arrange (SLinkListType &SL) { p = SL.r[0].next; // p指示第一个记录的当前位置 for ( i=1; i<Sl.length; ++i ) { while (p<i) p = SL.r[p].next; q = SL.r[p].next; // q指示尚未调整的表尾 if ( p!= i ) { SL.r[p]←→SL.r[i]; // 交换记录，使第i个记录到位 SL.r[i].next = p; // 指向被移走的记录 } p = q; // p指示尚未调整的表尾， // 为找第i+1个记录作准备 } // Arrange

9.2.3 希尔排序 希尔排序的思想 (1)对待排记录序列先作“宏观”调整，再作“微观”调整。 (2)所谓“宏观”调整，指的是，“跳跃式” 的插入排序。

9.2.3 希尔排序 希尔排序概述 (1)将记录序列分成若干子序列，分别对每个子序列进行插入排序。 例如：将 n 个记录分成 d 个子序列： {R[1],R[1+d],R[1+2d],…,R[1+kd]} {R[2],R[2+d],R[2+2d],…,R[2+kd]} …………………………………… {R[d],R[2d],R[3d],…,R[kd],R[(k+1)d]} (2)其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。

9.2.3 希尔排序 希尔排序演示 16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47

9.2.3 希尔排序 希尔排序算法 void ShellInsert ( SqList &L, int dk ) { for ( i=dk+1; i<=L.length; ++i ) if (LT(L.r[i].key, L.r[i-dk].key)) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j>0&&LT(L.r[0].key,L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 }

9.2.3 希尔排序 希尔排序算法 void ShellSort (SqList &L, int dlta[], int t) { // 增量为dlta[]的希尔排序 for (k=0; k<t; ++k) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 }

9.2.3 希尔排序 希尔排序算法分析 (1)稳定性 希尔排序是不稳定的排序方法。 (2)算法效率 (1)时间复杂度 平均O(n1.3)到平均O(n1.5) (2)空间复杂度 O(1)。

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.3 快速排序 9.3.1、起泡排序 9.3.2、快速排序

9.3.1 起泡排序 基本思想 (1)从第一个记录开始，两两记录比较，若F[1].key>F[2].key，则将两个记录交换； (2)第1趟比较结果将序列中关键字最大的记录放置到最后一个位置，称为“沉底”，而最小的则上浮一个位置; (3)n个记录比较n-1遍(趟)。

9.3.1 起泡排序 示例演示 1 6 2 3 4 5 1 2 6 3 4 5 1 2 3 6 4 5 1 2 3 4 6 5 1 2 3 4 5 6 6 1 2 3 4 5 第一趟 1 2 3 4 5 6 第二趟

9.3.1 起泡排序 算法 void BubbleSort(SqList &L ) {int i,j,noswap; SqList temp; for(i=1;i<=n-1;i++) {noswap=TRUE; for(j=1;j<=n-i;j++) if (L.r[j].key>L.r[j+1].key) {temp=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=temp; noswap=FALSE; } if (noswap) break;

9.3.1 起泡排序 算法分析 (1)稳定性 起泡排序是稳定的排序方法。 (2)时间是复杂性 最好情况：比较O(n),移动O(1) 最坏情况：比较O(n2),移动O(n2) 平均情况：O(n2) (3)空间复杂性 O(1)

(1)左侧子序列中所有对象的关键字都小于或等于对象v的关键字； (2)右侧子序列中所有对象的关键字都大于或等于对象v的关键字； 9.3.2 快速排序 基本思想 任取待排序对象序列中的某个对象v(枢轴，基准，支点)，按照该对象的关键字大小，将整个序列划分为左右两个子序列； (1)左侧子序列中所有对象的关键字都小于或等于对象v的关键字； (2)右侧子序列中所有对象的关键字都大于或等于对象v的关键字； (3)对象v则排在这两个子序列中间(也是它最终的位置)。

9.3.2 快速排序 示例演示 初始关键字 49 49* 65 97 17 27 50 i j j 一次交换 27 49* 65 97 17 49 50 i i j 二次交换 27 49* 49 97 17 65 50 i j 三次交换 27 49* 17 97 49 65 50 i j 四次交换 27 49* 17 49 97 65 50 i j 完成一趟排序

9.3.2 快速排序 算法关键语句 初始关键字 49 49* 65 97 17 27 50 low high high pivotkey=L.r[low].key; while ((low<high)&& (L.r[high].key>=pivotkey)) --high; L.r[low] ←→ L.r[high]; 一次交换 27 49* 65 97 17 49 50 low high low while ((low<high)&& (L.r[low].key<=pivotkey)) ++low; L.r[low] ←→ L.r[high];

while ((low<high)&& (L.r[high].key>=pivotkey)) --high; 9.3.2 快速排序 算 法 int Partition(SqList &L, int low, int high) { KeyType pivotkey; 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; } return low; // 返回枢轴位置 } // Partition

9.3.2 快速排序 算法分析 (1)稳定性 快速排序是不稳定的排序方法。 (2)时间复杂度 最坏情况： 1,2,3,…,n n,n-1,…2,1。 比较O(n2), 移动O(n2) n,n-1,…2,1。

9.3.2 快速排序 算法分析 时间复杂性最好情况是每次选择的基准把左右分成相等两部分： C(n)≤n+2C(n/2) ≤n+2(n/2+2C(n/4))=2n+22C(n/22) …… ≤kn+2kC(n/2k) 最后组中只有一个元素：n=2k,k=log2n, C(n)≤nlog2n+nC(1) 最好情况的时间复杂度为O(nlog2n) 平均时间复杂度也是O(nlog2n)

由于快速排序是一个递归过程，需一个栈的附加空间，栈的平均深度为O(log2n)。 9.3.2 快速排序 (3)空间复杂度 由于快速排序是一个递归过程，需一个栈的附加空间，栈的平均深度为O(log2n)。 QUICKSORT(s,t,A) LIST F; int s,t; {int i; if (s<t) {i=PARTITION(s,t,A); QUICKSORT(s,i-1,A); QUICKSORT(i+1,t,A); } 假如数组元素下标为1…n。 1 … n/2k n/2k-1 n/23 n/4 n/22 n/2 n

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.4 选择排序 9.4.1 简单选择排序 9.4.2 树形选择排序 9.4.3 堆排序

9.4.1 简单选择排序 基本思想 (1)第一次从n个关键字中选择一个最小值,确定第一个; (2)第二次再从剩余元素中选择一个最小值,确定第二个; (3)共需n-1次选择。

9.4.1 简单选择排序 操作过程 设需要排序的表是A[n+1]: (1)第一趟排序是在无序区A[1]到A[n]中选出最小的记录，将它与A[1]交换，确定最小值; (2)第二趟排序是在A[2]到A[n]中选关键字最小的记录，将它与A[2]交换，确定次小值； (3)第i趟排序是在A[i]到A[n]中选关键字最小的记录，将它与A[i]交换； (4)共n-1趟排序。

9.4.1 简单选择排序 算 法 void SelectSort(SqList &L) {int i,j,low; for(i=1;i<L.length;i++) {low=i; for(j=i+1;j<=L.length;j++) if(L.r[j].key<L.r[low].key) low=j; if(i!=low) {L.r[0]=L.r[i];L.r[i]=L.r[low];L.r[low]=L.r[0]; }

9.4.1 简单选择排序 算法分析 4. 算法分析 (1)稳定性 简单选择排序方法是稳定的。 (2)时间复杂度 比较O(n2),移动最好O(1),最差O(n) (3)空间复杂度 为O(1)。

9.4.2 树形选择排序 引入 树形选择排序，又称锦标赛排序:按锦标赛的思想进行排序，目的是减少选择排序中的重复比较次数。 例如： 4,3,1,2 在选择排序中3和4的比较次数共发生了三次。

9.4.2 树形选择排序 示例演示 6 6 8 9 6 17 8 6 10 9 20 8 9 90 17 输出6

9.4.2 树形选择排序 示例演示 8 9 8 9 20 17 8  10 9 20 8 9 90 17 输出8

9.4.2 树形选择排序 算法分析 (1)稳定性 树形选择排序方法是稳定的。 (2)时间复杂度 比较O(nlog2n) (3)空间复杂度 为O(n)。

9.4.3 堆排序 引 入 堆排序属于选择排序:出发点是利用前一次比较的结果，减少“比较”的次数。

9.4.3 堆排序 堆的定义 n个元素的序列A[1].key,A[2].key,…,A[n].key，当且仅当满足下述关系时，称之为堆。 A[i].key≤A[2*i].key 且 A[i].key≤A[2*i+1].key A[i].key≥A[2*i].key A[i].key≥A[2*i+1].key 小根堆 大根堆

9.4.3 堆排序 小根堆例子 0 1 2 3 4 5 6 7 8 12 22 34 40 30 36 50 41 12 22 34 40 30 36 50 41 小根(顶)堆

9.4.3 堆排序 大根堆例子 0 1 2 3 4 5 6 7 8 87 50 36 40 30 34 12 22 87 50 36 40 30 34 12 22 大根(顶)堆

9.4.3 堆排序 利用大根堆进行排序的示例演示 87 87 50 36 40 30 34 12 22 50 36 22 50 36 40 30 34 12 87 40 30 34 12 22 22 50 36 40 30 34 12 87

9.4.3 堆排序 堆排序的思想 堆排序需解决两个问题： (1) 由一个无序序列建成一个堆。 (2) 在输出堆顶元素之后，调整剩余元素成为一个新的堆。

9.4.3 堆排序 堆排序的算法(采用大根堆) (1) 按关键字建立A[1],A[2],…A[n]的大根堆; (2) 输出堆顶元素，采用堆顶元素A[1]与最后一个元素A[n]交换，最大元素得到正确的排序位置; (3) 此时前n-1个元素不再满足堆的特性，需重建堆; (4) 循环执行b,c两步，到排序完成。

9.4.3 堆排序 算法示例演示 例 对无序序列{50，38，48，97，49，13，27，65}进行堆排序。 (1)先建一个完全二叉树： 50 2)从最后一个非终端结点开始建堆； n个结点,最后一个非终端结点的下标是n/2 38 48 97 49 13 27 65

9.4.3 堆排序 算法示例演示 50 50 38 48 97 48 97 49 13 27 38 49 13 27 65 50 65 97 97 48 65 48 65 49 13 27 50 49 13 27 38 38

9.4.3 堆排序 算法示例演示 50 s 78 38 49 j s j 75 78 65 64 63 62 m j

9.4.3 堆排序 筛选算法 void HeapAdjust(HeapType &H, int s, int m) {int j; RedType rc; rc = H.r[s]; for (j=2*s; j<=m; j*=2) {if (j<m && H.r[j].key<H.r[j+1].key) ++j; if (rc.key >= H.r[j].key) break; H.r[s] = H.r[j]; s = j; } H.r[s] = rc; // 插入 } // HeapAdjust

9.4.3 堆排序 建堆算法代码 for (i=H.length/2; i>0; --i) HeapAdjust ( H, i, H.length );

9.4.3 堆排序 堆排序算法代码 void HeapSort(HeapType &H) { int i; RcdType temp; for (i=H.length/2; i>0; --i) HeapAdjust ( H, i, H.length ); for (i=H.length; i>1; --i) { temp=H.r[i];H.r[i]=H.r[1]; H.r[1]=temp; HeapAdjust(H, 1, i-1); } } // HeapSort

9.4.3 堆排序 算法分析 (1)堆排序是不稳定的排序。 (2)时间复杂度为O(nlog2n)。 最坏情况下时间复杂度为O(nlog2n)的算法。 (3)空间复杂度为O(1)。 {2，38，38} 38 2 38 2 38 38 38 2 38

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.5 归并排序 归并的定义 又叫合并，两个或两个以上的有序序列合并成一个有序序列。

for (j=m+1, k=i; i<=m && j<=n; ++k) { if LQ(SR[i].key,SR[j].key) 9.5 归并排序 归并示例演示 i m n SR[] 08 21 25 49 62 72 93 16 22 23 j i i j j j i for (j=m+1, k=i; i<=m && j<=n; ++k) { if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } i n TR[] 08 16 21 22 23 25 25 49 62 72 93 k k k k k

while (k<=n && i<=m) TR[k++]=SR[i++]; if (j<=n) 9.5 归并排序 归并示例演示 i m n SR[] 08 21 25 49 62 72 93 16 22 23 j i i j j j i if (i<=m) while (k<=n && i<=m) TR[k++]=SR[i++]; if (j<=n) while (k<=n &&j <=n) TR[k++]=SR[j++]; i n TR[] 08 16 21 22 23 25 25 49 62 72 93 k k k k k

9.5 归并排序 归并算法 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) { int j,k; ……………………….. } // Merge

9.5 归并排序 归并算法 for (j=m+1, k=i; i<=m && j<=n; ++k) { if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i<=m) while (k<=n && i<=m) TR[k++]=SR[i++]; if (j<=n) while (k<=n &&j <=n) TR[k++]=SR[j++];

给定排序码25，57，48，37，12，92，86，写出二路归并排序过程。 9.5 归并排序 2-路归并排序方法示例 例 给定排序码25，57，48，37，12，92，86，写出二路归并排序过程。 A[] 25 57 48 37 12 92 86 B[] 25 57 37 48 12 92 86 一趟 A[] 25 37 48 57 12 86 92 二趟 B[] 12 25 37 48 57 86 92 三趟

9.5 归并排序 2-路归并排序方法思想 (1) 将n个记录看成是n个长度为1的有序子表； (2) 将两两相邻的有序子表进行归并，若子表数为奇数，则留下的一个子表直接进入下一次归并； (3) 重复步骤(2)，直到归并成一个长度为n的有序表。

void Msort(RcdType A[],RcdType B[],int n, int l) {int i=1,t; 9.5 归并排序 2-路归并排序核心算法 void Msort(RcdType A[],RcdType B[],int n, int l) {int i=1,t; while (i+2*l-1<=n); {Merge (A,B,i,i+l-1,i+2*l-1) i=i+2*l; } …………………… R[] … i=1 l 2*l i+2l-1 i i+l-1

void Msort(RcdType A[],RcdType B[],int n, int l) {…………. 9.5 归并排序 2-路归并排序核心算法 void Msort(RcdType A[],RcdType B[],int n, int l) {…………. if (i+l-1<n) Merge(A,B,i,i+l-1,n); else for (t=i;t<=n;t++) B[t]=A[t]; } n … i+l-1 i+2l-1 i

9.5 归并排序 2-路归并排序算法 void MergeSort(RcdType A[],int n) {int l=1; Rcdtype B[]; while (l<n) {mpass(A,B,n,l) l=2*l; mpass(B,A,n,l); }

9.5 归并排序 2-路归并排序算法分析 (1) 稳定性 归并排序是稳定的排序方法。 (2) 时间复杂度 每趟归并所花时间比较移动都是O(n)； 归并趟数为log2n; 时间复杂度为O(nlog2n)。 (3) 空间复杂度是O(n)。

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.6.1 顺序基数排序 基数排序的起源 (1)基数起源于排序箱(桶)排序，设置若干个箱子(桶),依次扫描待排序的记录,A[1],A[2],…,A[n],把关键字为k的记录放在第k个箱子里,按序号将非空的箱子里的记录收集起来。 (2)箱(桶)排序的缺点：如果关键字位数太大，这样做空间复杂度和时间复杂度都太大。

9.6.1 顺序基数排序 事例演示 Q[0] 890 210 Q[1] 321 901 Q[2] 432 012 待排序关键字：321 986 123 432 543 018 765 678 987 789 098 890 109 901 210 012 Q[3] 123 543 Q[4] Q[5] 765 Q[6] 986 Q[7] 987 Q[8] 018 678 098 Q[9] 789 109

9.6.1 顺序基数排序 事例演示 Q[0] 901 109 Q[1] 210 012 018 Q[2] 321 123 890 210 321 901 432 012 123 543 765 986 987 018 678 098 789 109 Q[3] 432 Q[4] 543 Q[5] Q[6] 765 Q[7] 678 Q[8] 986 987 789 Q[9] 890 098

9.6.1 顺序基数排序 事例演示 Q[0] 012 018 098 Q[1] 109 123 Q[2] 210 Q[3] 321 901 109 210 012 018 123 543 765 678 986 987 789 809 098 Q[4] 432 Q[5] 543 Q[6] 678 Q[7] 765 789 Q[8] 890 Q[9] 901 986 987

9.6.1 顺序基数排序 排序过程 设待排记录A的关键字是figure位的正整数。 (1) 从最低位(个位)开始，扫描关键字的pass位,把等于0的插入Q[0],…,等于9的插入Q[9]。 (2) 将Q[0],…,Q[9]中的数据依次收集到A[]中。 (3) pass+1直到figure，重复执行1，2两步

return((k/pow10(p-1))%10); } 9.6.1 顺序基数排序 求关键字k的第p位算法 int RADIX(int k,int p) { return((k/pow10(p-1))%10); }

9.6.1 顺序基数排序 基数排序算法 void radixsort(int figure, QUEUE &A){ QUEUE Q[10];records data; int pass,r,i; //pass用于位数循环,r取位数 for(pass=1;pass<=figure;pass++) 把10个队列置空 while(!EMPTY(A)) { 取A中元素dada， 计算data的关键字的第pass位的值r， 放入队列Q[r]中； } 把10个队列中的值依次收集到A中 }

9.6.1 顺序基数排序 基数排序算法 void radixsort(int figure,QUEUE &A){ QUEUE Q[10];records data; int pass,r,i; //pass用于位数循环,r取位数 for(pass=1;pass<=firure;pass++){ for(i=0;i<=9;i++) MAKENULL(Q[i]) while(!EMPTY(A)) { data=FRONT(A); DEQUEUE(A); r=RADIX(data.key,pass); ENQUEUE(data,Q[r]); }

9.6.1 顺序基数排序 基数排序算法 For(i=0;i<=9;i++) While(!EMPTY(Q[i])) {data=FRONT(Q[i]); DEQUEUE(Q[i]); ENQUEUE(data,A); }

9.6.1 顺序基数排序 问题分析 如果采用顺序队列，队列的长度怎么确定？ 110 920 230 030 090 320 100 400 503 765 678 986 987 789 890 098 如果采用数组表示队列,队列的长度很难确定,太大造成浪费,小了会产生溢出。 一般采用链队列.

9.6.2 链式基数排序 存储结构 struct celltype{ records element; celltype *next } struct QUEUE{ celltype *front; celltype *rear; }

9.6.2 链式基数排序 事例演示 Q0 012 018 098 ^ Q1 109 123 ^ Q2 210

9.6.2 链式基数排序 收集算法关键语句 void CONCATENATE(QUEUE &Q[0], QUEUE &Q[1]){ if(!EMPTY(Q[1])){ Q[0].rear->next=Q[1].front->next; Q[0].rear=Q[1].rear; }

9.6.2 链式基数排序 两种收集算法的比较 For(i=0;i<=9;i++) While(!EMPTY(Q[i])) {data=FRONT(Q[i]); DEQUEUE(Q[i]); ENQUEUE(data,A); } 顺序收集算法 for(i=1;i<=9;i++) CONCATENATE(Q[0],Q[i]); A=Q[0]; 链式收集算法

9.6.2 链式基数排序 算法分析 基数排序是稳定的 时间复杂性与空间复杂性分析： 设关键字位数为d 则时间复杂性为O(dn) 考虑到d是一个常数 时间复杂性为O(n) 空间复杂性O(n)

第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较

9.7 内部排序方法的比较 n n2 n2 n n2 n2 n2 n2 n n n2 √ 1 √ 1 nlog2n × log2n 1 √ 比较次数 移动次数 稳定 性 附加存储 最好 最差 直接插入排序 冒泡排序 快速排序 简单选择排序 堆排序 归并排序 基数排序 n n2 n2 √ 1 n n2 n2 √ 1 nlog2n n2 n2 × log2n n n n2 1 √ nlog2n nlog2n 1 × nlog2n nlog2n √ n dn …… √ n

本章小结 熟练掌握：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序的思想和算法。充分了解各种排序算法的应用背景和优缺点。 加强各种排序算法在实际应用中的训练，提高实际应用水平。