1
11.6 基数排序
11.1 排序的基本概念
11.2 插入排序
11.3 交换排序
11.4 选择排序
11.5 归并排序
11.7 各种内排序方法的比较和选择第十一章 内排序
2
所谓 排序,就是要整理表中的记录,使之按关键字递增 (或递减 )有序排列。其确切定义如下：
输入,n个记录,R0,R1,…,Rn-1,其相应的关键字分别为 k0,k1,…,kn-1。
输出,Rio,Ri1,…,Ri,n-1,使得 ki0≤ki1≤… ≤ki,n-1
(或 ki0≥ki1≥… ≥ki,n-1)。
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”
的记录序列。
11.1 排序的基本概念
3
当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。
如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的 相对次序保持不变,则称这种排序方法是 稳定的 ；反之,若具有相同关键字的记录之间的 相对次序发生变化,则称这种排序方法是 不稳定的 。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
4
内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
有序序列区 无 序 序 列 区一趟排序有 序 序列区 无 序 序列区逐步扩大记录有序序列长度的方法大致有下列几类：
插入类 交换类选择类 归并类 其他方法内部排序,若 整个排序过程不需要访问外存 便能完成，则称此类排序问题为 内部排序 。
外部排序,待排序纪录的数量很大，以致内存一次不能容纳全部纪录，在排序过程中尚需对外存进行访问的排序过程。
5
1.插入类将无序子序列中的 一个或几个记录,插入,
到有序序列中，从而增加记录的有序子序列的长度。
3.交换类通过,交换,无序序列中的记录从而得到其中关键字最小 或 最大 的记录，并将它 加入到有序子序列中,以此方法增加记录的有序子序列的长度。
2.选择类从记录的无序子序列中,选择,关键字最小 或最大 的记录，并将它 加入到有序子序列中,以此方法增加记录的有序子序列的长度。
6
4.归并类通过,归并,两个或两个以上的记录有序子序列，逐步增加记录的有序序列的长度。
5.其他方法
11.2 插入排序插入排序的基本思想,每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的有序表中，直到全部记录插入完成为止。
7
11.2.1 直接插入排序
一趟直接插入排序的基本思想：
有序序列 R[0..i-1] 无序序列 R[i,..n-1]
R[i]
有序序列 R[0..i] 无序序列 R[i+1,..n-1]
实现“一趟插入排序”可分三步进行：
1,在 R[0..i-1]中查找 R[i]的插入位臵 ;
R[0..j] ≤R[i] <R[j+1..i-1]
2,将 R[j+1..i-1]中的所有记录均后移一个位臵 ;
3,将 R[i]复制到 R[j+1]的位臵上。
8
11.2.1 直接插入排序利用 顺序查找 实现“在 R[0..i-1]中查找 R[i]的插入位臵”
void InsertSort(RecType R[],int n)
{ int i,j; RecType temp;
for (i=1;i<n;i++) //进行 n-1趟排序
{temp=R[i]; j=i-1;
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; //记录后移
j--;
}
R[j+1]=temp; //插入到正确位置
}
}
9
void InsertSort(RecType R[],int n)
{ int i,j; RecType temp;
for (i=1;i<n;i++) //进行 n-1趟排序
{temp=R[i]; j=i-1;
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; j--; }
R[j+1]=temp; }
} 49 38 65 97 76 13 27
i=1 (49) 38 65 97 76 13 274938
temp
38
jj
0 1 2 3 4 5 6
i=3 (38 49 65） 97 76 13 27
i=2 (38 49） 65 97 76 13 27
i=4 (38 49 65 97） 76 13 27
i=5 13 (13 38 49 65 76 97) 27
i=6 (13 27 38 49 65 76 97)27
977676
65
97
10
算法评价
时间复杂度
若待排序记录按关键字从小到大排列 (正序 )
关键字比较次数,111
1
n
n
i?记录移动次数,2（ n-1）
若待排序记录按关键字从大到小排列 (逆序 )
关键字比较次数,2 )1(1
1
nnin
i
记录移动次数：
若待排序记录是随机的，取平均值
T(n)=O(n2)
空间复杂度,S(n)=O(1)
2
)1)(4()2(1
1
+?+
nnin
i
11
希尔排序 (缩小增量排序 )
基本思想,对待排记录序列先作“宏观”调整，
再作“微观”调整。
所谓“宏观”调整，指的是“跳跃式”的插入排序。 具体做法为：
将记录序列分成若干个子序列，分别对每个子序列进行插入排序其中,d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。
{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[(1+k)d]}
例如，将 n个记录分为 d个子序列,
取 d3=1
三趟分组,4 13 38 27 49’ 55 49 65 97 76
三趟排序,4 13 27 38 49’ 49 55 65 76 97
例,初始状态,4 38 65 97 76 13 27 49’ 55 49
一趟排序,4 27 49’ 55 49 13 38 65 97 76
二趟排序,4 13 38 27 49’ 55 49 65 97 76
一趟分组,4 38 65 97 76 13 27 49’ 55 49
取 d1=5
二趟分组：
取 d2=2
4 27 49’ 55 49 13 38 65 97 76
13
希尔排序特点
子序列的构成不是简单的“逐段分割”，
而是将相隔某个增量的记录组成一个子序列
希尔排序可提高排序速度，因为
分组后 n值减小,n2更小，而 T(n)=O(n2),
所以 T(n)从总体上来说是减小了
关键字较小的记录跳跃式前移，在进行最后一趟增量为 1的插入排序时，序列已基本有序
增量序列取法
无除 1以外的公因子
最后一个增量值必须为 1
希尔排序是不稳定的如（ 5,2,2）。
14
11.3 交换排序交换排序的基本思想,两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的纪录为止。 1,冒泡排序 2,快速排序
1,冒泡排序假设在排序过程中，记录序列 R[0..n-1]的状态为：
有序序列 R[0..i-1] 无序序列 R[i,..n-1]
i-1
第 i趟起泡排序 比较相邻记录，将关键字最小的记录交换到 i的位臵上有 序 序 列 R[0..i]无序序列 R[i+1,..n-1]
15
void BubbleSort(RecType R[],int n)
{ int i,j； RecType temp;
for (i=0;i<n-1;i++)
{ for (j=n-1;j>i;j--)
if (R[j].key<R[j-1].key)
{ temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
}
}
}
5 12 23 36 17 8
初始关键字 a[]
a 6
i=0
j从 5～ 1
0 1 2 3 4 5
8 178 368 28 18
i=1
j从 5～ 2
17 3617 23
i=2
j从 5～ 3
i=3
j从 5～ 4
i=4
j取 5
i=5 结束由该例我们看出第 3趟排序时，该序列就已经排好了，但仍执行第 4、第 5趟排序。
16
void BubbleSort1(RecType R[],int n)
{ int i,j,exchange;RecType temp;
for (i=0;i<n-1;i++)
{ exchange=0;
for (j=n-1;j>i;j--)
if (R[j].key<R[j-1].key)
{temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
exchange=1;
}
if (exchange==0) return; /*中途结束算法 */
}
}
改进的冒泡排序
5 12 23 36 17 8
初始关键字 a[]
a 6
i=0
j从 5～ 1
0 1 2 3 4 5
8 178 368 238 18
i=1
j从 5～ 2
17 3617 23
i=2
j从 5～ 3
该趟排序没有交换数据,
exchange=0,程序结束 。
17
算法评价
–时间复杂度
>>最好情况（正序）
比较次数,n-1
移动次数,0
>>最坏情况（逆序）
比较次数,)(
2
1)( 21
1
nnin
n
i
)(23)(3 2
1
nnin
n
i
移动次数：
–空间复杂度,S(n)=O(1)
T(n)=O(n2)
18
2,快速排序一趟快速排序：
目标,找一个记录，以它的关键字作为,枢轴,,凡其 关键字小于枢轴 的记录均 移动至该记录之前,反之，凡 关键字大于枢轴 的记录均 移动至该记录之后 。致使一趟排序之后，记录的无序序列 R[s..t]将 被分割成两部分,R[s..i-1]和 R[i+1..t]
且 R[j].key≤R[i].key≤R[j].key
s≤j≤i-1 枢轴 i+1≤j≤t
19
排序过程,设待排序列为,{R[s],R[s+1],…R[t]},
设两个指针 i和 j,设 基准 记录 temp=任意序列元素,
再从 i所指位臵起 向后搜索,找到第一个关键字大于 temp.key的记录,和 R[j]交换,
再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止,
首先从 j所指位臵 向前搜索 第一个关键字 小于
temp.key的记录，并和 R[i]交换,
初始时令 i=s,j=t.
重复上述两步，直至 i==j为止,
20
3 5 6 1 4 2 7 9 8 0
temp=L->data[0]=3
0 5
61 3
i ji i i jjjjjj
2
21
算法评价
– 时间复杂度
最好情况（每次总是选到中间值作基准）
T(n)=O(nlog2n)
最坏情况（每次总是选到最小或最大元素作基准） T(n)=O(n2)
平均,T(n)=O(nlog2n)
– 空间复杂度：需栈空间以实现递归
最坏情况,S(n)=O(n)
一般情况,S(n)=O(log2n)
快速排序是不稳定的，举例 2 2 1
22
11.4 选择排序选择排序的基本思想是,每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕。
两种选择排序方法：
(1)直接选择排序 (或称简单选择排序 )
(2)堆排序
23
1,直接选择排序假设在排序过程中，待排记录序列 R[0..n-1]的状态为：
第 i趟直接选择排序从中选出关键字最小的记录有 序 序 列 R[0..i-1] 无序序列 R[i,..n-1]
有 序 序 列 R[0..i] 无序序列 R[i+1,..n-1]
24
直接选择排序过程,
首先通过 n-1次关键字比较，从无序区 R[0~n-
1] 中找出关键字最小的记录，将它与第一个记录交换 ；
再通过 n-2次比较，从无序区 R[1~n-1]中找出关键字次小的记录，将它与第二个记录交换 ；
重复上述操作，共进行 n-1趟排序后，最终序列变成有序序列，排序结束。
一趟,[ 49 38 65 97 76 13 27 ]
k
j j j j j j
i=0 13 49
二趟,13 [38 65 97 76 49 27 ]i=1
k k
j j j jj
27 38
i=2 三趟,13 27 [65 97 76 49 38 ]
i=3 四趟,13 27 38 [97 76 49 65 ]
i＝ 4 五趟,13 27 38 49 [76 97 65 ]
i＝ 5 六趟,13 27 38 49 65 [97 76 ]
排序结束,13 27 38 49 65 76 97
k k例：初始,[ 49 38 65 97 76 13 27 ]
26
算法评价
时间复杂度
记录移动次数
)(21)1( 2
2
0
nnin
n
i
空间复杂度,S(n)=O(1)
T(n)=O(n2)
1 3 5 7 9 11(有序 )
7 9 11 5 3 1(反序 )
直接选择排序不稳定，例如,2 2 1
最好情况,0
最坏情况,3(n-1)
比较次数：
27
堆的定义,n个 关键字 的序列 {k1,k2,……k n},当且仅当满足下列关系时，称之为堆
+ 12
2
ii
ii
kk
kk
+ 12
2
ii
ii
kk
kk或例 {96,83,27,38,11,9}
96
27
91138
83
若将序列对应的一维数组看成是一个完全二叉树的顺序存储结构，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于 (或不小于 )其左、
右孩子的结点的值。
故堆顶元素必为序列的最小 (大 )值。
2,堆排序逻辑结构物理结构
96 83 27 38 11 9
0 1 2 3 4 5 6
28
堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？
如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
堆排序堆排序利用了大根堆 (或小根堆 )堆顶记录的关键字最大 (或最小 )这一特征，使得在当前无序区中选取最大 (或最小 )关键字的记录变得简单。
大根堆排序算法的基本操作：
① 初始化操作：将 R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录 R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆 (亦称重建堆 )。
第二个问题解决方法 —— 筛选方法,输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树根结点的大者进行比较，若前者小则交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例 9
78
3156
29
2 tmp 28
6
2 8
3 37
3
7
1 16
5
16
30
第二个问题解决方法 —— 筛选方法,输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树根结点的大者进行比较，若前者小则交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例 9
78
3156
29
28
6
5 8
37
3
7
16
2
16
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
31
第一个问题解决方法方法,从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含 8个元素的无序序列（ 6,8,7,9,1,5,3,2）
6
78
3519
2
6
78
3519
2
6
78
3519
2
6
79
3518
2
9
78
3516
2
for(i=n/2;i>=1;i--)
SIFT(R,i,n);
程序的实现：
32
void HeapSort(RecType R[ ],int n)
{ int i; RecType temp;
for (i=n/2;i>=1;i--) /*循环建立初始堆 */
sift(R,i,n);
for (i=n;i>=2;i--) /*进行 n-1次循环,完成推排序 */
{ temp=R[1]; //将当前区间最后一个元素同 R[1]对换
R[1]=R[i]; R[i]=temp;
sift(R,1,i-1); /*筛选 R[1]结点,得到 i-1个结点的堆 */
}
}
完整的堆排序算法：
1.建堆
2,筛选
时间复杂度：最坏情况下
T(n)=O(nlog2n)
空间复杂度,S(n)=O(1)
不稳定
适用于记录数较大的情况
33
11.5 归并排序
归并 —— 将两个或两个以上的有序表组合成一个新的有序表。
2-路归并排序排序过程
设初始序列含有 n个记录，则可看成 n个有序的子序列，每个子序列长度为 1
两两合并，得到?n/2? 个长度为 2或 1的有序子序列
再两两合并,…… 如此重复，直至得到一个长度为 n的有序序列为止
34
例 初始关键字,[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]
LA
LB
LC
i
k
j j+1>
i+1
35
算法的实现
– 2-路归并排序的核心操作是将一维数组中前后相邻的两个有序子序列归并为一个有序序列，
算法为
– 一趟归并问题：设各有序子序列长度为 length(最后一个序列可能小于 length)，则共有?n/length?个有序的子序列待归并，一趟归并的具体算法如下：
36
二路归并排序算法如下：
void MergeSort(RecType R[],int n)
/*自底向上的二路归并算法 */
{
int length;
for (length=1;length<n;length=2*length)
MergePass(R,length,n);
}
37
11.6 基数排序
多关键字排序基数排序 是通过,分配,和,收集,过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。
一般情况下，假设有 n个记录的序列 {R1,R2,…,R n}
且每个记录 Ri中含有 d个关键字（ Kid-1,Kid-2,…,
Ki0 ），则称序列 {R1,R2,…,R n}对关键字（ Kid-1,Kid-
2,…,K i0）有序是指：对于序列中任意两个记录 Ri和
Rj(1≤i＜ j≤n)都满足下列有序关系,( Kid-1,Kid-2,…,
Ki0)<(Kjd-1,Kjd-2,…,K j0)
其中,Kd-1称为 最主位关键字,K0称为 最次位关键字 。如 56210和 32556。
38
基数排序有两种,最低位优先 (LSD)和最高位优先 (MSD)。
最低位优先 (LSD)的过程是,先按最低位的值对记录进行排序,在此基础上,再按次低位进行排序,依此类推。由低位向高位,每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序,直至最高位,则完成了基数排序的整个过程。
2位十进制数的 LSD的排序过程如下：
假设线性表由结点序列 a0,a1,…,a n-l构成,每个结点 aj的关键字由 2位十进制数组成,排序过程中,
使用 10个队列 Q0,Q1,…,Q 9。
39
设臵 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾指针 。
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至 10个链队列中，每个队列记录的关键字的个位相同 。
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，
重新将 10个队列链成一个链表 。
重复上述两步，进行第二趟分配和收集，对十位进行 排序,最后得到一个有序序列例 初始状态：
75 23 98 44 57 12 29 64 38 82
p
链队头指针
hd[0] hd[1] hd[2] hd[3] hd[4] hd[5] hd[6] hd[7] hd[8] hd[9]
链队尾指针
tl[0] tl[1] tl[2] tl[3] tl[4] tl[5] tl[6] tl[7] tl[8] tl[9]
7523 9844 5712 29
64 3882
按个位收集：
12 82 23 44 64 75 57 98 38 29
p
链队头指针
hd[0] hd[1] hd[2] hd[3] hd[4] hd[5] hd[6] hd[7] hd[8] hd[9]
链队尾指针
tl[0] tl[1] tl[2] tl[3] tl[4] tl[5] tl[6] tl[7] tl[8] tl[9]
12
按个位收集：
12 82 23 44 64 75 57 98 38 29
p
8223 44 64 75 9838
29
按十位收集：
12 23 29 38 44 57 64 75 82 98
p
57
42
算法评价
时间复杂度,
分配,T(n)=O(n)
收集,T(n)=O(r)
T(n)=O(d(n+r))
其中,n—— 记录数
d—— 关键字 位 数
r—— 关键字取值范围
空间复杂度,S(n)=2r个队列指针 +n个指针域空间
11.7 各种内部排序方法的比较排序方法 平均时间 最好情况 最坏情况 辅助空间直接插入排序 O(n2) O(n) O(n2) O(1)
希尔排序 O(nlog2n) O(nlog2n) ---- O(1)
起泡排序 O(n2) O(n) O(n2) O(1)
快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)
简单选择排序 O(n2) O(n2) O(n2) O(1)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd)
说明：
1,简单排序：指所有时间复杂度为 O(n2)的排序方法，
包括直接插入排序、起泡排序、简单选择排序。
2.从平均时间性能来说，快速排序最佳，其所需时间最省，但在最坏情况下（基本有序 /有序）的时间性能不如归并排序和堆排序。
而对于归并排序和堆排序来说，在 n较大时，归并排序所需时间较堆排序省，但这是以需要的辅助空间多为代价。
排序方法 平均时间 最好情况 最坏情况 辅助空间直接插入排序 O(n2) O(n) O(n2) O(1)
希尔排序 O(nlog2n) O(nlog2n) ---- O(1)
起泡排序 O(n2) O(n) O(n2) O(1)
快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)
简单选择排序 O(n2) O(n2) O(n2) O(1)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd))O(d(n+rd)) O(rd)
45
本 章 小 结：
各种排序方法的原理和过程
时间复杂度、空间复杂度
稳定性从稳定性的角度来看：
不稳定的算法有：简单选择排序、希尔排序、
快速排序、堆排序导致不稳定的主要因素：比较或交换时不是在相邻的两个纪录之间进行。
11.6 基数排序
11.1 排序的基本概念
11.2 插入排序
11.3 交换排序
11.4 选择排序
11.5 归并排序
11.7 各种内排序方法的比较和选择第十一章 内排序
2
所谓 排序,就是要整理表中的记录,使之按关键字递增 (或递减 )有序排列。其确切定义如下：
输入,n个记录,R0,R1,…,Rn-1,其相应的关键字分别为 k0,k1,…,kn-1。
输出,Rio,Ri1,…,Ri,n-1,使得 ki0≤ki1≤… ≤ki,n-1
(或 ki0≥ki1≥… ≥ki,n-1)。
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”
的记录序列。
11.1 排序的基本概念
3
当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。
如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的 相对次序保持不变,则称这种排序方法是 稳定的 ；反之,若具有相同关键字的记录之间的 相对次序发生变化,则称这种排序方法是 不稳定的 。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
4
内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
有序序列区 无 序 序 列 区一趟排序有 序 序列区 无 序 序列区逐步扩大记录有序序列长度的方法大致有下列几类：
插入类 交换类选择类 归并类 其他方法内部排序,若 整个排序过程不需要访问外存 便能完成，则称此类排序问题为 内部排序 。
外部排序,待排序纪录的数量很大，以致内存一次不能容纳全部纪录，在排序过程中尚需对外存进行访问的排序过程。
5
1.插入类将无序子序列中的 一个或几个记录,插入,
到有序序列中，从而增加记录的有序子序列的长度。
3.交换类通过,交换,无序序列中的记录从而得到其中关键字最小 或 最大 的记录，并将它 加入到有序子序列中,以此方法增加记录的有序子序列的长度。
2.选择类从记录的无序子序列中,选择,关键字最小 或最大 的记录，并将它 加入到有序子序列中,以此方法增加记录的有序子序列的长度。
6
4.归并类通过,归并,两个或两个以上的记录有序子序列，逐步增加记录的有序序列的长度。
5.其他方法
11.2 插入排序插入排序的基本思想,每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的有序表中，直到全部记录插入完成为止。
7
11.2.1 直接插入排序
一趟直接插入排序的基本思想：
有序序列 R[0..i-1] 无序序列 R[i,..n-1]
R[i]
有序序列 R[0..i] 无序序列 R[i+1,..n-1]
实现“一趟插入排序”可分三步进行：
1,在 R[0..i-1]中查找 R[i]的插入位臵 ;
R[0..j] ≤R[i] <R[j+1..i-1]
2,将 R[j+1..i-1]中的所有记录均后移一个位臵 ;
3,将 R[i]复制到 R[j+1]的位臵上。
8
11.2.1 直接插入排序利用 顺序查找 实现“在 R[0..i-1]中查找 R[i]的插入位臵”
void InsertSort(RecType R[],int n)
{ int i,j; RecType temp;
for (i=1;i<n;i++) //进行 n-1趟排序
{temp=R[i]; j=i-1;
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; //记录后移
j--;
}
R[j+1]=temp; //插入到正确位置
}
}
9
void InsertSort(RecType R[],int n)
{ int i,j; RecType temp;
for (i=1;i<n;i++) //进行 n-1趟排序
{temp=R[i]; j=i-1;
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; j--; }
R[j+1]=temp; }
} 49 38 65 97 76 13 27
i=1 (49) 38 65 97 76 13 274938
temp
38
jj
0 1 2 3 4 5 6
i=3 (38 49 65） 97 76 13 27
i=2 (38 49） 65 97 76 13 27
i=4 (38 49 65 97） 76 13 27
i=5 13 (13 38 49 65 76 97) 27
i=6 (13 27 38 49 65 76 97)27
977676
65
97
10
算法评价
时间复杂度
若待排序记录按关键字从小到大排列 (正序 )
关键字比较次数,111
1
n
n
i?记录移动次数,2（ n-1）
若待排序记录按关键字从大到小排列 (逆序 )
关键字比较次数,2 )1(1
1
nnin
i
记录移动次数：
若待排序记录是随机的，取平均值
T(n)=O(n2)
空间复杂度,S(n)=O(1)
2
)1)(4()2(1
1
+?+
nnin
i
11
希尔排序 (缩小增量排序 )
基本思想,对待排记录序列先作“宏观”调整，
再作“微观”调整。
所谓“宏观”调整，指的是“跳跃式”的插入排序。 具体做法为：
将记录序列分成若干个子序列，分别对每个子序列进行插入排序其中,d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。
{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[(1+k)d]}
例如，将 n个记录分为 d个子序列,
取 d3=1
三趟分组,4 13 38 27 49’ 55 49 65 97 76
三趟排序,4 13 27 38 49’ 49 55 65 76 97
例,初始状态,4 38 65 97 76 13 27 49’ 55 49
一趟排序,4 27 49’ 55 49 13 38 65 97 76
二趟排序,4 13 38 27 49’ 55 49 65 97 76
一趟分组,4 38 65 97 76 13 27 49’ 55 49
取 d1=5
二趟分组：
取 d2=2
4 27 49’ 55 49 13 38 65 97 76
13
希尔排序特点
子序列的构成不是简单的“逐段分割”，
而是将相隔某个增量的记录组成一个子序列
希尔排序可提高排序速度，因为
分组后 n值减小,n2更小，而 T(n)=O(n2),
所以 T(n)从总体上来说是减小了
关键字较小的记录跳跃式前移，在进行最后一趟增量为 1的插入排序时，序列已基本有序
增量序列取法
无除 1以外的公因子
最后一个增量值必须为 1
希尔排序是不稳定的如（ 5,2,2）。
14
11.3 交换排序交换排序的基本思想,两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的纪录为止。 1,冒泡排序 2,快速排序
1,冒泡排序假设在排序过程中，记录序列 R[0..n-1]的状态为：
有序序列 R[0..i-1] 无序序列 R[i,..n-1]
i-1
第 i趟起泡排序 比较相邻记录，将关键字最小的记录交换到 i的位臵上有 序 序 列 R[0..i]无序序列 R[i+1,..n-1]
15
void BubbleSort(RecType R[],int n)
{ int i,j； RecType temp;
for (i=0;i<n-1;i++)
{ for (j=n-1;j>i;j--)
if (R[j].key<R[j-1].key)
{ temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
}
}
}
5 12 23 36 17 8
初始关键字 a[]
a 6
i=0
j从 5～ 1
0 1 2 3 4 5
8 178 368 28 18
i=1
j从 5～ 2
17 3617 23
i=2
j从 5～ 3
i=3
j从 5～ 4
i=4
j取 5
i=5 结束由该例我们看出第 3趟排序时，该序列就已经排好了，但仍执行第 4、第 5趟排序。
16
void BubbleSort1(RecType R[],int n)
{ int i,j,exchange;RecType temp;
for (i=0;i<n-1;i++)
{ exchange=0;
for (j=n-1;j>i;j--)
if (R[j].key<R[j-1].key)
{temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
exchange=1;
}
if (exchange==0) return; /*中途结束算法 */
}
}
改进的冒泡排序
5 12 23 36 17 8
初始关键字 a[]
a 6
i=0
j从 5～ 1
0 1 2 3 4 5
8 178 368 238 18
i=1
j从 5～ 2
17 3617 23
i=2
j从 5～ 3
该趟排序没有交换数据,
exchange=0,程序结束 。
17
算法评价
–时间复杂度
>>最好情况（正序）
比较次数,n-1
移动次数,0
>>最坏情况（逆序）
比较次数,)(
2
1)( 21
1
nnin
n
i
)(23)(3 2
1
nnin
n
i
移动次数：
–空间复杂度,S(n)=O(1)
T(n)=O(n2)
18
2,快速排序一趟快速排序：
目标,找一个记录，以它的关键字作为,枢轴,,凡其 关键字小于枢轴 的记录均 移动至该记录之前,反之，凡 关键字大于枢轴 的记录均 移动至该记录之后 。致使一趟排序之后，记录的无序序列 R[s..t]将 被分割成两部分,R[s..i-1]和 R[i+1..t]
且 R[j].key≤R[i].key≤R[j].key
s≤j≤i-1 枢轴 i+1≤j≤t
19
排序过程,设待排序列为,{R[s],R[s+1],…R[t]},
设两个指针 i和 j,设 基准 记录 temp=任意序列元素,
再从 i所指位臵起 向后搜索,找到第一个关键字大于 temp.key的记录,和 R[j]交换,
再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止,
首先从 j所指位臵 向前搜索 第一个关键字 小于
temp.key的记录，并和 R[i]交换,
初始时令 i=s,j=t.
重复上述两步，直至 i==j为止,
20
3 5 6 1 4 2 7 9 8 0
temp=L->data[0]=3
0 5
61 3
i ji i i jjjjjj
2
21
算法评价
– 时间复杂度
最好情况（每次总是选到中间值作基准）
T(n)=O(nlog2n)
最坏情况（每次总是选到最小或最大元素作基准） T(n)=O(n2)
平均,T(n)=O(nlog2n)
– 空间复杂度：需栈空间以实现递归
最坏情况,S(n)=O(n)
一般情况,S(n)=O(log2n)
快速排序是不稳定的，举例 2 2 1
22
11.4 选择排序选择排序的基本思想是,每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕。
两种选择排序方法：
(1)直接选择排序 (或称简单选择排序 )
(2)堆排序
23
1,直接选择排序假设在排序过程中，待排记录序列 R[0..n-1]的状态为：
第 i趟直接选择排序从中选出关键字最小的记录有 序 序 列 R[0..i-1] 无序序列 R[i,..n-1]
有 序 序 列 R[0..i] 无序序列 R[i+1,..n-1]
24
直接选择排序过程,
首先通过 n-1次关键字比较，从无序区 R[0~n-
1] 中找出关键字最小的记录，将它与第一个记录交换 ；
再通过 n-2次比较，从无序区 R[1~n-1]中找出关键字次小的记录，将它与第二个记录交换 ；
重复上述操作，共进行 n-1趟排序后，最终序列变成有序序列，排序结束。
一趟,[ 49 38 65 97 76 13 27 ]
k
j j j j j j
i=0 13 49
二趟,13 [38 65 97 76 49 27 ]i=1
k k
j j j jj
27 38
i=2 三趟,13 27 [65 97 76 49 38 ]
i=3 四趟,13 27 38 [97 76 49 65 ]
i＝ 4 五趟,13 27 38 49 [76 97 65 ]
i＝ 5 六趟,13 27 38 49 65 [97 76 ]
排序结束,13 27 38 49 65 76 97
k k例：初始,[ 49 38 65 97 76 13 27 ]
26
算法评价
时间复杂度
记录移动次数
)(21)1( 2
2
0
nnin
n
i
空间复杂度,S(n)=O(1)
T(n)=O(n2)
1 3 5 7 9 11(有序 )
7 9 11 5 3 1(反序 )
直接选择排序不稳定，例如,2 2 1
最好情况,0
最坏情况,3(n-1)
比较次数：
27
堆的定义,n个 关键字 的序列 {k1,k2,……k n},当且仅当满足下列关系时，称之为堆
+ 12
2
ii
ii
kk
kk
+ 12
2
ii
ii
kk
kk或例 {96,83,27,38,11,9}
96
27
91138
83
若将序列对应的一维数组看成是一个完全二叉树的顺序存储结构，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于 (或不小于 )其左、
右孩子的结点的值。
故堆顶元素必为序列的最小 (大 )值。
2,堆排序逻辑结构物理结构
96 83 27 38 11 9
0 1 2 3 4 5 6
28
堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？
如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
堆排序堆排序利用了大根堆 (或小根堆 )堆顶记录的关键字最大 (或最小 )这一特征，使得在当前无序区中选取最大 (或最小 )关键字的记录变得简单。
大根堆排序算法的基本操作：
① 初始化操作：将 R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录 R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆 (亦称重建堆 )。
第二个问题解决方法 —— 筛选方法,输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树根结点的大者进行比较，若前者小则交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例 9
78
3156
29
2 tmp 28
6
2 8
3 37
3
7
1 16
5
16
30
第二个问题解决方法 —— 筛选方法,输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树根结点的大者进行比较，若前者小则交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
例 9
78
3156
29
28
6
5 8
37
3
7
16
2
16
1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
31
第一个问题解决方法方法,从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含 8个元素的无序序列（ 6,8,7,9,1,5,3,2）
6
78
3519
2
6
78
3519
2
6
78
3519
2
6
79
3518
2
9
78
3516
2
for(i=n/2;i>=1;i--)
SIFT(R,i,n);
程序的实现：
32
void HeapSort(RecType R[ ],int n)
{ int i; RecType temp;
for (i=n/2;i>=1;i--) /*循环建立初始堆 */
sift(R,i,n);
for (i=n;i>=2;i--) /*进行 n-1次循环,完成推排序 */
{ temp=R[1]; //将当前区间最后一个元素同 R[1]对换
R[1]=R[i]; R[i]=temp;
sift(R,1,i-1); /*筛选 R[1]结点,得到 i-1个结点的堆 */
}
}
完整的堆排序算法：
1.建堆
2,筛选
时间复杂度：最坏情况下
T(n)=O(nlog2n)
空间复杂度,S(n)=O(1)
不稳定
适用于记录数较大的情况
33
11.5 归并排序
归并 —— 将两个或两个以上的有序表组合成一个新的有序表。
2-路归并排序排序过程
设初始序列含有 n个记录，则可看成 n个有序的子序列，每个子序列长度为 1
两两合并，得到?n/2? 个长度为 2或 1的有序子序列
再两两合并,…… 如此重复，直至得到一个长度为 n的有序序列为止
34
例 初始关键字,[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]
LA
LB
LC
i
k
j j+1>
i+1
35
算法的实现
– 2-路归并排序的核心操作是将一维数组中前后相邻的两个有序子序列归并为一个有序序列，
算法为
– 一趟归并问题：设各有序子序列长度为 length(最后一个序列可能小于 length)，则共有?n/length?个有序的子序列待归并，一趟归并的具体算法如下：
36
二路归并排序算法如下：
void MergeSort(RecType R[],int n)
/*自底向上的二路归并算法 */
{
int length;
for (length=1;length<n;length=2*length)
MergePass(R,length,n);
}
37
11.6 基数排序
多关键字排序基数排序 是通过,分配,和,收集,过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。
一般情况下，假设有 n个记录的序列 {R1,R2,…,R n}
且每个记录 Ri中含有 d个关键字（ Kid-1,Kid-2,…,
Ki0 ），则称序列 {R1,R2,…,R n}对关键字（ Kid-1,Kid-
2,…,K i0）有序是指：对于序列中任意两个记录 Ri和
Rj(1≤i＜ j≤n)都满足下列有序关系,( Kid-1,Kid-2,…,
Ki0)<(Kjd-1,Kjd-2,…,K j0)
其中,Kd-1称为 最主位关键字,K0称为 最次位关键字 。如 56210和 32556。
38
基数排序有两种,最低位优先 (LSD)和最高位优先 (MSD)。
最低位优先 (LSD)的过程是,先按最低位的值对记录进行排序,在此基础上,再按次低位进行排序,依此类推。由低位向高位,每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序,直至最高位,则完成了基数排序的整个过程。
2位十进制数的 LSD的排序过程如下：
假设线性表由结点序列 a0,a1,…,a n-l构成,每个结点 aj的关键字由 2位十进制数组成,排序过程中,
使用 10个队列 Q0,Q1,…,Q 9。
39
设臵 10个队列,f[i]和 e[i]分别为第 i个队列的头指针和尾指针 。
第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至 10个链队列中，每个队列记录的关键字的个位相同 。
第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，
重新将 10个队列链成一个链表 。
重复上述两步，进行第二趟分配和收集，对十位进行 排序,最后得到一个有序序列例 初始状态：
75 23 98 44 57 12 29 64 38 82
p
链队头指针
hd[0] hd[1] hd[2] hd[3] hd[4] hd[5] hd[6] hd[7] hd[8] hd[9]
链队尾指针
tl[0] tl[1] tl[2] tl[3] tl[4] tl[5] tl[6] tl[7] tl[8] tl[9]
7523 9844 5712 29
64 3882
按个位收集：
12 82 23 44 64 75 57 98 38 29
p
链队头指针
hd[0] hd[1] hd[2] hd[3] hd[4] hd[5] hd[6] hd[7] hd[8] hd[9]
链队尾指针
tl[0] tl[1] tl[2] tl[3] tl[4] tl[5] tl[6] tl[7] tl[8] tl[9]
12
按个位收集：
12 82 23 44 64 75 57 98 38 29
p
8223 44 64 75 9838
29
按十位收集：
12 23 29 38 44 57 64 75 82 98
p
57
42
算法评价
时间复杂度,
分配,T(n)=O(n)
收集,T(n)=O(r)
T(n)=O(d(n+r))
其中,n—— 记录数
d—— 关键字 位 数
r—— 关键字取值范围
空间复杂度,S(n)=2r个队列指针 +n个指针域空间
11.7 各种内部排序方法的比较排序方法 平均时间 最好情况 最坏情况 辅助空间直接插入排序 O(n2) O(n) O(n2) O(1)
希尔排序 O(nlog2n) O(nlog2n) ---- O(1)
起泡排序 O(n2) O(n) O(n2) O(1)
快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)
简单选择排序 O(n2) O(n2) O(n2) O(1)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd)
说明：
1,简单排序：指所有时间复杂度为 O(n2)的排序方法，
包括直接插入排序、起泡排序、简单选择排序。
2.从平均时间性能来说，快速排序最佳，其所需时间最省，但在最坏情况下（基本有序 /有序）的时间性能不如归并排序和堆排序。
而对于归并排序和堆排序来说，在 n较大时，归并排序所需时间较堆排序省，但这是以需要的辅助空间多为代价。
排序方法 平均时间 最好情况 最坏情况 辅助空间直接插入排序 O(n2) O(n) O(n2) O(1)
希尔排序 O(nlog2n) O(nlog2n) ---- O(1)
起泡排序 O(n2) O(n) O(n2) O(1)
快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n)
简单选择排序 O(n2) O(n2) O(n2) O(1)
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+rd)) O(d(n+rd))O(d(n+rd)) O(rd)
45
本 章 小 结：
各种排序方法的原理和过程
时间复杂度、空间复杂度
稳定性从稳定性的角度来看：
不稳定的算法有：简单选择排序、希尔排序、
快速排序、堆排序导致不稳定的主要因素：比较或交换时不是在相邻的两个纪录之间进行。
