Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 1页第 3章 排序
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 2页
3.1 排序的基本概念
排序 是计算机内经常进行的一种操作，其目的是将一组,无序,的记录序列调整为,有序,
的记录序列 。
例如,将下列关键字序列
52,49,80,36,14,58,61,23,97,75
调整为
14,23,36,49,52,58,61,75,80,97
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 3页
3.1 排序的基本概念一般情况下，假设含 n个记录的序列为
{ R1,R2,…,Rn }
其相应的关键字序列为
{ K1,K2,…,Kn }
这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系,
Kp1≤K p2≤ … ≤K pn
按此固有关系将上式记录序列重新排列为
{ Rp1,Rp2,…,Rpn }
的操作称作排序。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 4页
C语言描述
#define MAXSIZE 1000 // 待排顺序表最大长度
typedef int KeyType; // 关键字类型为整数类型
/***********************************************/
typedef struct {
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项
} RcdType; // 记录类型
/***********************************************/
typedef struct {
RcdType r[MAXSIZE+1]; // r[0]闲置
int length; // 顺序表长度
} SqList; // 顺序表类型
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 5页
3.1 排序的基本概念
内部排序若整个排序过程 不需要访问外存 便能完成，则称此类排序问题为 内部排序 ；
外部排序反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序 。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 6页
3.1 排序的基本概念
内部排序的过程是一个逐步扩大记录的有序序列长度的过程 。
经过一趟排序有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 7页选择排序（ select sort)
有序序列 R[1..i] 无序序列 R[i+1..n]
有序序列 R[1..i-1] 无序序列 R[i..n]
R[j]R[i]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 8页算法 3.1
void SelectPass( SqList &L,int i ) {
// 已知 L.r[1..i-1]中记录按关键字非递减有序，本算法实现第 i 趟
//选择排序,即在 L.r[i..n]的记录中选出关键字最小的记录 L.r[j]
//和 L.r[i]交换
RcdType W；
j = i； // j 指示关键字最小记录的位置，初值设为 I
for ( k=i+1; k<=L.length; k++ )
if ( L.r[k].key < L.r[j].key ) j = k ；
// 暂不进行记录交换，只记录位置
if ( i != j ) { W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； }
// 最后互换记录 R[j] 和 R[i]
} // SelectPass
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 9页算法 3.2
void SelectSort (SqList &L) {
// 对顺序表 L作简单选择排序。
RcdType W；
for (i=1; i<=L.length;++i ){ // 选择第 i小的记录，并交换到位
j=i;
for ( k=i+1; k<=L.length; k++ )
// 在 L.r[i..L.length]中选择 key最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ；
if ( i!=j )
{ W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； }
// 与第 i个记录交换 }
} // SelectSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 10页内部排序过程中主要进行下列两种基本操作,
1.比较两个关键字的大小
2.将元素从一个位置移动到另一个位置。
内部排序按时间复杂度来划分可分为：
1,简单排序方法 O（ n2）
2,先进排序方法 O（ nlogn）
3,基数排序（ d*n）
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 11页
3.2 简单排序方法
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 12页
3.2.1 插入排序方法有序序列 R[1..i-1]
R[i]
无序序列 R[i..n]
一趟直接插入排序的基本思想,
有序序列 R[1..i] 无序序列 R[i+1..n]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 13页实现“一趟插入排序”可分三步进行：
1．在 R[1..i-1]中 查找 R[i]的插入位置，
R[1..j].key? R[i].key < R[j+1..i-1].key；
2．将 R[j+1..i-1]中的所有 记录 均 后移 一个位置；
3．将 R[i] 插入 (复制 )到 R[j+1]的位置上。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 14页直接插入排序
算法的实现要点：
从 R[i-1]起向前进行顺序查找,监视哨设置在 R[0]；
R[0] = R[i]; // 设置,哨兵,
for (j=i-1; R[0].key<R[j].key; --j);
// 从后往前找循环结束表明 R[i]的插入位置为 j +1
R[0]
j
R[i]
j=i-1插入位置
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 15页
对于在查找过程中找到的那些关键字不小于 R[i].key的记录，并在查找的同时实现记录向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
上述循环结束后可以直接进行“插入”
令 i = 2,3,…,n,
实现整个序列的排序。
for ( i=2; i<=n; ++i )
if (R[i].key<R[i-1].key)
{ 在 R[1..i-1]中查找 R[i]的插入位置 ;
插入 R[i] ; }
R[0]
j
R[i]
j= i-1插入位置
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 16页算法 3.3
void InsertPass( SqList &L,int i ) {
// 已知 L.r[1..i-1]中的记录已按关键字非递减的顺序有
// 序排列，本算法实现 将 L.r[i]插入其中，并保持
// L.r[1..i]中记录按关键字非递减顺序有序
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];
// 插入到正确位置
} // InsertPass
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 17页算法 3.4
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]; // 复制为哨兵
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]; // 插入到正确位置
} // if
} // InsertSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 18页例 49 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27
i=3 65 (38 49 65) 97 76 13 27
i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
i=6 13 (13 38 49 65 76 97) 27
i=1 ( )
i=7 (13 38 49 65 76 97) 2727
jj j jjj
977665493827
(13 27 38 49 65 76 97)排序结果：
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 19页
算法评价
– 时间复杂度
若待排序记录按关键字从小到大排列 (正序 )
关键字比较次数：
11
2
nn
i
记录移动次数,0
若待排序记录按关键字从大到小排列 (逆序 )
关键字比较次数：
记录移动次数：
2
)1)(4()1(
2
nnin
i
若待排序记录是随机的，取平均值
关键字比较次数：
4
2n
记录移动次数：
4
2n
T(n)=O(n2)
– 空间复杂度,S(n)=O(1)
2
)1)(4()1(
2
nnin
i
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 20页
3.2.2 起泡排序
假设在排序过程中，记录序列 R[1..n]的状态为：
比较相邻记录，将关键字最大的记录 交换到 n-i+1 的位置上第 i 趟起泡排序无序序列 R[1..n-i+1] 有序序列 R[n-i+2..n]
n-i+1
无序序列 R[1..n-i] 有序序列 R[n-i+1..n]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 21页算法 3.5
void BubbleSort( SqList &L ){
// 对顺序表 L作起泡排序,
RcdType W； 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) {
W=L.r[j]； L.r[j] =L.r[j+1]； L.r[j+1] = W；
// 互换记录
lastExchangeIndex = j; } //if
} // for
i = lastExchangeIndex;
// 一趟排序中无序序列中最后一个记录的位置
} // while
}// BubbleSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 22页
1 49
2 38
3 27
4 66
5 15
6 94
7 53
8 72
9 81
1 49
2 38
3 27
4 66
5 15
6 94
7 53
8 72
9 81
1 38
2 27
3 49
4 15
5 66
6 53
7 72
8 81
9 94
1 27
2 38
3 15
4 49
5 53
6 66
7 72
8 81
9
1 27
2 15
3 38
4 49
5 53
6
7
8
9
38
27
49
15
66
53
72
81
94
27
38
15
49
53
66
15
38
15
27
i
i
i
i
算法 3.5
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 23页注意,
2,一般情况下，每经过一趟“起泡”，
,i 减一”,但并不是每趟都如此。
例如,
5 2 3 1 9 7 82 53 1 5 7 98 9
i=7i=6
for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …
1 3
i=2
1,起泡排序的结束条件为，
最后一趟没有进行“交换记录”。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 24页时间分析,
最好的情况（关键字在记录序列中顺序有序）：
只需进行一趟起泡
“比较”的次数：
最坏的情况（关键字在记录序列中逆序有序）：
需进行 n-1趟起泡
“比较”的次数：
0
“移动”的次数：
“移动”的次数：
n-1
2
)1()1(2
nni
ni 2
)1(3)1(3 2
nni
ni
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 25页
3.3 先进的排序方法
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 26页
3.3.1 快速排序
基本思想：
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 27页排序过程：
对 r[s……t] 中记录进行一趟快速排序，附设两个指针 i和 j,设枢轴记录 rp=r[s],x=rp.key
– 初始时令 i=s,j=t
– 首先从 j所指位置向前搜索第一个关键字小于 x的记录，并和 rp
交换
– 再从 i所指位置起向后搜索，找到第一个关键字大于 x的记录，
和 rp交换
– 重复上述两步，直至 i==j为止
– 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 28页算法 3.6
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
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 29页
31 68 45 90 23 39 54 12 87 76
31暂存枢轴记录 R[0]
low highhighhigh
12
12
low
68
68
highhighhigh
23
23
low
45
45
highhigh
31
31
快速排序的“一次划分过程”如下所示,
31
算法 3.6
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 30页算法 3.7
void QSort (RcdType R[],int s,int t ) {
// 对记录序列 R[s..t]进行快速排序
if (s < t-1) { // 长度大于 1
pivotloc = Partition(R,s,t);
// 对 R[s..t] 进行一次划分，并返回枢轴位置
QSort(R,s,pivotloc-1); // 对低子序列递归排序
QSort(R,pivotloc+1,t); // 对高子序列递归排序
} // if
} // Qsort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 31页例 初始关键字,49 38 65 97 76 13 27 50
i j
x
ji
完成一趟排序,( 27 38 13) 49 (76 97 65 50)
分别进行快速排序,( 13) 27 (38) 49 (50 65) 76 (97)
快速排序结束,13 27 38 49 50 65 76 97
4927
i i ji
49 65
j
13 4949 97
i j
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 32页算法 3.8
void QuickSort( SqList & L) {
// 对顺序表 L 进行快速排序
QSort(L.r,1,L.length);
} // QuickSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 33页快速排序的时间分析结论,快速排序的时间复杂度为
O(nlogn)
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 1页第 3章 排序
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 2页
3.1 排序的基本概念
排序 是计算机内经常进行的一种操作，其目的是将一组,无序,的记录序列调整为,有序,
的记录序列 。
例如,将下列关键字序列
52,49,80,36,14,58,61,23,97,75
调整为
14,23,36,49,52,58,61,75,80,97
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 3页
3.1 排序的基本概念一般情况下，假设含 n个记录的序列为
{ R1,R2,…,Rn }
其相应的关键字序列为
{ K1,K2,…,Kn }
这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系,
Kp1≤K p2≤ … ≤K pn
按此固有关系将上式记录序列重新排列为
{ Rp1,Rp2,…,Rpn }
的操作称作排序。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 4页
C语言描述
#define MAXSIZE 1000 // 待排顺序表最大长度
typedef int KeyType; // 关键字类型为整数类型
/***********************************************/
typedef struct {
KeyType key; // 关键字项
InfoType otherinfo; // 其它数据项
} RcdType; // 记录类型
/***********************************************/
typedef struct {
RcdType r[MAXSIZE+1]; // r[0]闲置
int length; // 顺序表长度
} SqList; // 顺序表类型
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 5页
3.1 排序的基本概念
内部排序若整个排序过程 不需要访问外存 便能完成，则称此类排序问题为 内部排序 ；
外部排序反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序 。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 6页
3.1 排序的基本概念
内部排序的过程是一个逐步扩大记录的有序序列长度的过程 。
经过一趟排序有序序列区 无 序 序 列 区有序序列区 无 序 序 列 区
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 7页选择排序（ select sort)
有序序列 R[1..i] 无序序列 R[i+1..n]
有序序列 R[1..i-1] 无序序列 R[i..n]
R[j]R[i]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 8页算法 3.1
void SelectPass( SqList &L,int i ) {
// 已知 L.r[1..i-1]中记录按关键字非递减有序，本算法实现第 i 趟
//选择排序,即在 L.r[i..n]的记录中选出关键字最小的记录 L.r[j]
//和 L.r[i]交换
RcdType W；
j = i； // j 指示关键字最小记录的位置，初值设为 I
for ( k=i+1; k<=L.length; k++ )
if ( L.r[k].key < L.r[j].key ) j = k ；
// 暂不进行记录交换，只记录位置
if ( i != j ) { W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； }
// 最后互换记录 R[j] 和 R[i]
} // SelectPass
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 9页算法 3.2
void SelectSort (SqList &L) {
// 对顺序表 L作简单选择排序。
RcdType W；
for (i=1; i<=L.length;++i ){ // 选择第 i小的记录，并交换到位
j=i;
for ( k=i+1; k<=L.length; k++ )
// 在 L.r[i..L.length]中选择 key最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ；
if ( i!=j )
{ W=L.r[j]； L.r[j] =L.r[i]； L.r[i] = W； }
// 与第 i个记录交换 }
} // SelectSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 10页内部排序过程中主要进行下列两种基本操作,
1.比较两个关键字的大小
2.将元素从一个位置移动到另一个位置。
内部排序按时间复杂度来划分可分为：
1,简单排序方法 O（ n2）
2,先进排序方法 O（ nlogn）
3,基数排序（ d*n）
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 11页
3.2 简单排序方法
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 12页
3.2.1 插入排序方法有序序列 R[1..i-1]
R[i]
无序序列 R[i..n]
一趟直接插入排序的基本思想,
有序序列 R[1..i] 无序序列 R[i+1..n]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 13页实现“一趟插入排序”可分三步进行：
1．在 R[1..i-1]中 查找 R[i]的插入位置，
R[1..j].key? R[i].key < R[j+1..i-1].key；
2．将 R[j+1..i-1]中的所有 记录 均 后移 一个位置；
3．将 R[i] 插入 (复制 )到 R[j+1]的位置上。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 14页直接插入排序
算法的实现要点：
从 R[i-1]起向前进行顺序查找,监视哨设置在 R[0]；
R[0] = R[i]; // 设置,哨兵,
for (j=i-1; R[0].key<R[j].key; --j);
// 从后往前找循环结束表明 R[i]的插入位置为 j +1
R[0]
j
R[i]
j=i-1插入位置
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 15页
对于在查找过程中找到的那些关键字不小于 R[i].key的记录，并在查找的同时实现记录向后移动；
for (j=i-1; R[0].key<R[j].key; --j);
R[j+1] = R[j]
上述循环结束后可以直接进行“插入”
令 i = 2,3,…,n,
实现整个序列的排序。
for ( i=2; i<=n; ++i )
if (R[i].key<R[i-1].key)
{ 在 R[1..i-1]中查找 R[i]的插入位置 ;
插入 R[i] ; }
R[0]
j
R[i]
j= i-1插入位置
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 16页算法 3.3
void InsertPass( SqList &L,int i ) {
// 已知 L.r[1..i-1]中的记录已按关键字非递减的顺序有
// 序排列，本算法实现 将 L.r[i]插入其中，并保持
// L.r[1..i]中记录按关键字非递减顺序有序
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];
// 插入到正确位置
} // InsertPass
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 17页算法 3.4
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]; // 复制为哨兵
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]; // 插入到正确位置
} // if
} // InsertSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 18页例 49 38 65 97 76 13 27
i=2 38 (38 49) 65 97 76 13 27
i=3 65 (38 49 65) 97 76 13 27
i=4 97 (38 49 65 97) 76 13 27
i=5 76 (38 49 65 76 97) 13 27
i=6 13 (13 38 49 65 76 97) 27
i=1 ( )
i=7 (13 38 49 65 76 97) 2727
jj j jjj
977665493827
(13 27 38 49 65 76 97)排序结果：
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 19页
算法评价
– 时间复杂度
若待排序记录按关键字从小到大排列 (正序 )
关键字比较次数：
11
2
nn
i
记录移动次数,0
若待排序记录按关键字从大到小排列 (逆序 )
关键字比较次数：
记录移动次数：
2
)1)(4()1(
2
nnin
i
若待排序记录是随机的，取平均值
关键字比较次数：
4
2n
记录移动次数：
4
2n
T(n)=O(n2)
– 空间复杂度,S(n)=O(1)
2
)1)(4()1(
2
nnin
i
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 20页
3.2.2 起泡排序
假设在排序过程中，记录序列 R[1..n]的状态为：
比较相邻记录，将关键字最大的记录 交换到 n-i+1 的位置上第 i 趟起泡排序无序序列 R[1..n-i+1] 有序序列 R[n-i+2..n]
n-i+1
无序序列 R[1..n-i] 有序序列 R[n-i+1..n]
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 21页算法 3.5
void BubbleSort( SqList &L ){
// 对顺序表 L作起泡排序,
RcdType W； 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) {
W=L.r[j]； L.r[j] =L.r[j+1]； L.r[j+1] = W；
// 互换记录
lastExchangeIndex = j; } //if
} // for
i = lastExchangeIndex;
// 一趟排序中无序序列中最后一个记录的位置
} // while
}// BubbleSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 22页
1 49
2 38
3 27
4 66
5 15
6 94
7 53
8 72
9 81
1 49
2 38
3 27
4 66
5 15
6 94
7 53
8 72
9 81
1 38
2 27
3 49
4 15
5 66
6 53
7 72
8 81
9 94
1 27
2 38
3 15
4 49
5 53
6 66
7 72
8 81
9
1 27
2 15
3 38
4 49
5 53
6
7
8
9
38
27
49
15
66
53
72
81
94
27
38
15
49
53
66
15
38
15
27
i
i
i
i
算法 3.5
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 23页注意,
2,一般情况下，每经过一趟“起泡”，
,i 减一”,但并不是每趟都如此。
例如,
5 2 3 1 9 7 82 53 1 5 7 98 9
i=7i=6
for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …
1 3
i=2
1,起泡排序的结束条件为，
最后一趟没有进行“交换记录”。
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 24页时间分析,
最好的情况（关键字在记录序列中顺序有序）：
只需进行一趟起泡
“比较”的次数：
最坏的情况（关键字在记录序列中逆序有序）：
需进行 n-1趟起泡
“比较”的次数：
0
“移动”的次数：
“移动”的次数：
n-1
2
)1()1(2
nni
ni 2
)1(3)1(3 2
nni
ni
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 25页
3.3 先进的排序方法
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 26页
3.3.1 快速排序
基本思想：
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 27页排序过程：
对 r[s……t] 中记录进行一趟快速排序，附设两个指针 i和 j,设枢轴记录 rp=r[s],x=rp.key
– 初始时令 i=s,j=t
– 首先从 j所指位置向前搜索第一个关键字小于 x的记录，并和 rp
交换
– 再从 i所指位置起向后搜索，找到第一个关键字大于 x的记录，
和 rp交换
– 重复上述两步，直至 i==j为止
– 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 28页算法 3.6
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
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 29页
31 68 45 90 23 39 54 12 87 76
31暂存枢轴记录 R[0]
low highhighhigh
12
12
low
68
68
highhighhigh
23
23
low
45
45
highhigh
31
31
快速排序的“一次划分过程”如下所示,
31
算法 3.6
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 30页算法 3.7
void QSort (RcdType R[],int s,int t ) {
// 对记录序列 R[s..t]进行快速排序
if (s < t-1) { // 长度大于 1
pivotloc = Partition(R,s,t);
// 对 R[s..t] 进行一次划分，并返回枢轴位置
QSort(R,s,pivotloc-1); // 对低子序列递归排序
QSort(R,pivotloc+1,t); // 对高子序列递归排序
} // if
} // Qsort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 31页例 初始关键字,49 38 65 97 76 13 27 50
i j
x
ji
完成一趟排序,( 27 38 13) 49 (76 97 65 50)
分别进行快速排序,( 13) 27 (38) 49 (50 65) 76 (97)
快速排序结束,13 27 38 49 50 65 76 97
4927
i i ji
49 65
j
13 4949 97
i j
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 32页算法 3.8
void QuickSort( SqList & L) {
// 对顺序表 L 进行快速排序
QSort(L.r,1,L.length);
} // QuickSort
Da
ta
Str
uc
tur
e
数据结构——
第
3
章排序胡建华 2009-7-24计算机教研室第 33页快速排序的时间分析结论,快速排序的时间复杂度为
O(nlogn)
