第十章 内部排序

10.1
概述
三.待排记录序列的存储方式
①待排记录放于地址连续的存储单元中； ②待排记录放于链表，记录之间的次序关系由 指针指示。 ③待排记录存放在地址连续的存储单元中，同时 另设一个指示各个记录存储位置的地址向量。
10.1
概述
四. 顺序存储结构表示待排记录
#define MAXSIZE 20 //顺序表的最大长度 typedef int KeyType; //定义关键字类型为整数类型 typedef struct{ KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; //记录类型 typedef struct{ RedType r[MAXSIZE+1]; //r[0]闲置或用作监视哨 int length; //顺序表长度 }SqList; //顺序表类型
基本有序指已接近正序：1,2,8,4,5,6,7,3,9 局部有序指某些部分有序：6,7,8,9,1,2,3,4,5
10.2
插入排序
二.希尔排序（缩小增量排序）
待解决问题：
问题1：如何使待排记录个数较少； 问题2：如何分割待排序列；
问题3：子序列内如何进行直接插入排序。
例
初始关键字 49 49 38 38 65 97 一趟排序结果 65 97 76 76 13 13 27 49 27 49
初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟 关键字 排序后 排序后 排序后 排序后 排序后 排序后
算法：
void Bubble_Sort(SqList &L) { for(i=L.length-1,change=TRUE;i>=1&&change;--i) { change=FALSE; for(j=0;j<i; ++j) { if (L.r[j+1]. key<L.r[j].key) { L.r[j]↔L.r[j+1]; change=TRUE; } } } }

L.r[j+1]=L.r[j]; //将j……i-1的记录后移一格 L.r[j+1]=L.r[0]; } //将Ri插入到位置j+1 }
-
算法效率
时间复杂度
待排序记录按关键字从小到大排列(正序)
n
比较次数: 1 n 1 i2
移动次数: 0
待排序记录按关键字从大到小排列(逆序)
比较次数:
n i (n2)(n1)
i2
2
移动次数:
n
(n4)(n1)
(i1)
i2
2
待排序记录随机，取平均值
比较次数: n 2
4
移动次数: n 2
4
总的时间复杂度:T(n)=O(n2)
空间复杂度：S(n)=O(1)
-
3. 折半插入排序
排序过程：用折半查找方法确定插入位置。 举例：
i=1: (38) (49) 38 65 97 76 13 27 49
5 R’={5}
R={10,2}
2 R’={2,5}
R={2}
10 R’={2,5,10}
R={ }
2 R’={2,2,5,10}
-
2. 直接插入排序
排序过程：整个排序过程为n-1趟插入
将序列中第1个记录看成是一个有序子序列 从第2个记录开始，逐个进行插入，直至整个序列有序
R1 R2 …… Rn
内部排序适用于记录个数不很多的小文件； 外部排序则适用于记录个数太多，不能一次 将其全部放入内存的大文件
排序依据策略
插入排序：直接插入排序, 折半插入排序, 希尔排序 交换排序：冒泡排序, 快速排序 选择排序：简单选择排序, 堆排序 归并排序：2-路归并排序 基数排序

希尔排序C 语言实现
/* 31,15,7,3,1 … */ void shell_sort(void) { int t, k, i, j, dk, rc; t = 0; while ((1 << t) < n) t++; for (k = 1; k < t; k++) { dk = (1 << (t - k)) - 1; for (i = dk + 1; i <= n; i++) { if (r[i] < r[i - dk]) { rc = r[i]; for (j = i - dk; j > 0 && rc < r[j]; j -= dk) r[j + dk] = r[j]; r[j + dk] = rc; } } }
起泡排序
原理: 序列中有n个元素，进行n-1趟(条件满足时可以提前结束) 第1趟，针对r[1～n]元素进行。 第2趟，针对r[1～(n-1)]元素进行。 …… 第n-1趟，针对 r[1～2]元素进行。 每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元 素的相对位置不正确，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换 时间复杂性: 正序时 O(n)，逆序时 O(n2)。平均时间复杂性 O(n2)
dk = delta(k); /* 增量序列函数，如: ……15,7,3,1 */
for (i = dk + 1; i <= n; i++) { rc = r[i]; for (j = i - dk; j > 0 && rc < r[j]; j -= dk)

第十章 内部排序
知识点1：概述 知识点2：插入排序 知识点3：快速排序 知识点4：选择排序 知识点5：归并排序 知识点6：基数排序 知识点7：各种内部排序方法的比较讨论
知识点1：概述
1、排序的定义： 将一个数据元素（或记录）的任意序列，重新排列成一个按关键字
有序的序列叫~。 例如将下列关键字序列
{ 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 } 调整为
4、排序分类
按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序
按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序
❖按排序所需工作量 简单的排序方法：T(n)=O(n²) 先进的排序方法：T(n)=O(nlog2n) 基数排序：T(n)=O(d.n)
知识点同的分类方法、排序的基 本过程。
{ 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 }
2、稳定性
若对于数据元素序列，使用某种排序方法，对它按关键字进行排序， 若相同关键字元素间的位置关系，排序前与排序后保持一致，称此排 序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。
3、排序基本操作：
•比较两个关键字大小 •将记录从一个位置移动到另一个位置

14
若待排序记录是随机的,取平均值。 n2 关键字比较次数约为: 4 n2 记录移动次数约为:
4
适合场合:当要排序的序列基本有序时,比较次数少。 当待排序记录的数量n很大时,不适合。
2013-7-5
15
10.2.2 其它插入排序
1、折半插入排序 稳定的排序方法 基本思想 用折半查找方法确定插入位置的排序。
20 20
20
39
42
85 )
16
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>=high+1;--j ) L.r[j+1] = L.r[j];//记录后移 L.r[high+1] = L.r[0]; // 插入 } } // 2013-7-5 BInsertSort 17
2013-7-5
19
初始关键字
49
38
65
97
76
13
27
49
i=1
i=2
(49)
firstfinal

归并排序为稳定算法，但在一般情况下很少利 用2—路归并排序来操作，因其算法实用性较差。
10.6 基数排序
基数排序是借助多关键字排序的思想对单逻辑 关键字进行排序的方法。
例 对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（ <<< ）
第一趟收集 30 63 83 74 94 25 05 78 18 09 89 69
0 12 34
第二趟分配 05 18 25 30 针对十位数 09
56789
63 74 83 94 69 78 89
0 1 2 3 4 5 6 7 8 9 10 11
第二趟收集 05 09 18 25 30 63 69 74 78 83 89 94
例 2—路归并排序算法
初始关键字 一趟归并后 二趟归并后
[49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] [ 38 49 65 97 ] [ 13 27 76 ]
三趟归并后
[13 27 38 49 65 76 97]
特点：
49 38 65 97 76 13 27 49
27
38
27
38 65 76 27
49 38 65 97 76 ∞ 27 49
10.4
三.堆排序 堆的概念：
选择排序
堆是满足下列性质的数列{k1,k2,…,kn}:
ki≤k2i ki≤k2i+1
或
ki≥k2i ki≥k2i+1

最坏的情况（关键码在记录序列中逆序有序）：
“比较”次数为(n+2)(n-1)/2 ，“移动”次数为(n+4)(n-1)/2 总的说来，直接插入排序所需进行关键码间的比较次数和记录移动次数均
为n2/4，所以直接插入排序的时间复杂度为O(n2)。 空间效率：需要一个记录的辅助空间，因此空间复杂度为O(1)
性能分析： 时间效率 最好的情况只需进行一趟起泡：“比较”次数为n-1，“移动”次数为0
最坏的情况需进行n-1趟起泡：“比较”的次数为
数与“比较”的次数 相同 。 “移动”次数是“交换”次数的 3倍 所以时间复杂度为：O(n2)—因为要考虑最坏情况
“交换”次
空间效率： O(1)—只在交换时用到一个缓冲单元 稳定性：稳定的
10.3.2 快速排序 基本思想：任取待排序序列中的某个元素作为基准（一般取第一个 元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元
素的排序码均小于基准元素的排序码，右子序列的排序码则大于等于基
准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列 有序。 例子：初始序列
第1次交换后 第2次交换后 第3次交换后 第4次交换后 完成一趟排序 【 46 i 【 17 i 【 17 【 17 【 17 【 17 i 05 i 05 05 13 13 42 55 i 13 13 42 42 94 94 i j 94 55 55 70 】 70 】 05 j 13 42 94 05 j 55 j 55 70 】 70 】 基准元素 55 13 42 94 05 17 j 70 】 j 70 】
例子： 初态
第一趟结果 第二趟结果
[49 38 65 97 76 13 27 49] 13[38 65 97 76 49 27 49] 13 27[65 97 76 49 38 49]

折半插入排序只能减少排序过程中关键字比较的次数，并不能减少 记录移动的次数，因此折半插入排序的时间复杂度仍为O (n2)
希尔排序
基本思想 先取一个正整数d1<n作为第一个增量，把所有相隔d1 的记录放一组，组内进行直接插入排序；然后取d2<d1作 为第二个增量，重复上述分组和排序操作；直至di=1，即 所有记录放进一个组中排序为止。
13 20 30 39
void BInsertSort (SqList &L) { // 对顺序表L作折半插入排序 for ( i=2; i<=L.length; ++i ) // 共需L.length-1趟排序 { 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
（60,50,40,30,20,10） » 若待排序记录按关键字从大到小排列(逆序) n 1 (n 2)(n 1) ( i 1) 关键字比较次数：
2 (n 4)(n 1) ( i 2) 记录移动次数： 2 i 1

初始关键字序列：
12345678 49 38 65 97 76 13 27 49*
第一趟排序后：
38 49 65 76 13 27 49* 97
第二趟排序后：
38 49 65 13 27 49* 76 97
第三趟排序后：
38 49 13 27 49* 65 76 97
第四趟排序后：
38 13 27 49 49* 65 76 97
10.2 希尔排序算法
void ShellInsert(SqList &L,int dk) {//对顺序表L作一+i 1<i=<L=.eLn.getnhg;tih+;+i+) +)
iiff((LL..rr[[ii]]..kkeeyy<<LL..rr[[ii--d1k]]..kkeeyy)){{//需将L.r[i]插入有序增量子表
10.1 排序的基本概念(续)
正序与逆序
➢ 若有序表是按排序码升序排列的，则称为升序表或正序 表，否则称为降序表或逆序表。不失普遍性，我们一般 只讨论正序表。
排序方法度量
➢ 排序过程主要是比较记录的关键字和移动记录。因此排 序的时间复杂性可以算法执行中的数据比较次数及数据 移动次数来衡量。当一种排序方法使排序过程在最坏或 平均情况下所进行的比较和移动次数越少，则认为该方 法的时间复杂性就越好。
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0]; }//if
最好情况} 下// (I正ns序er)tSort
最坏情况下(逆序)
元素的❖ 比分较析次直数接为插: 入n 排- 1序算法中关键元字素的的比比较较次次数数和: 记(录n+移2动)(次n-数1)/2

再分别对两个子序列进行快速排序， 直到每个子序列只含有一个记录为止
42
x 例 初始关键字： 2479 38 146395 4997 76 941793 246795 50
i i i iij j j j j 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 97
重复上述过程，直到“在一趟排序过程中没有进行 过交换记录的操作”为止
37
例 1 4398 38 38 38 3183 13 2 3489 49 49 4193 132387 27 3 65 65 6153 142397 23780 30 4 9776 7163 162357 243790 3308 38 5 719637 172367 263750 3409 49 6 19237 732607 3605 65 7 293770 3706 76 8 3907 97

{ int i,j,k;
JD x;
//中间变量
for(k=0;k<T;k++) //T等于几，进行几趟shell排序
{ for(i=d[k]+1;i<=n;i++)
{ x=r[i];
j=i-d[k];
//直接插入排序法j=i-1
33
while((j>0)&&(x.key<r[j].key))
{ r[j+d[k]]=r[j]; //直接插入排序法r[j+1]=r[j]
5
01 23 4 5 36 24 10 6 12 i