二叉排序树上的删除，相当于删去
有序序列上的一个记录，应保证删
除结点后，二叉排序树的特性不变。
删除结点可有三种情况,
1.若被删除结点 *p为叶子结点，即其 pL和
pR均为空树。由于叶子结点的存在若不
破坏整株树的结构，则只需修改其父结
点的指针即可。
2.若 *p结点只有左子树 pL或只有右子树 pR，
此时只要令 pL或 pR直接成为其父结点 *f
的左子树即可。可见，也不破坏二叉排序
树的特性。
3.若 *p结点的左、右子树均不空，不能简
单处理，可有两种情况。例,
F
P
f
p
pL pR
(a)
f
F
P
C
p
c
CL Q
PR
q
S Q
L
SL
S
F
C
c
CL S
S
f
SL PR
(b) (c)
f
F
S
C
p
c
CL Q
PR
q
QL SL
(d)
二叉排序树中删除一个
结点的算法
DeleteBST(T,key)
{ if(!T) return False;
else { if(EQ(key,T->data.key))
return Delete(T);
if(LT(key,T->data.key))
return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);}
}//DeleteBST
上述三种情况的删除算法
Delete(p)/*p被删除点 */
{ if(!p->rchild) /*右子树空接其左子树 */
{q=p;p=p->lchild;free(q);}
else if(!p->lchild)/*只接其右子树 */
{ q=p;p=p->rchild;free(q);}
else
{ q=p; s=p->lchild;
while(s->rchild)
{ q=s; s=p->lchild;}
/*转左，然后向右到尽头 */
p->data= s->data;/*s指向删除结点的前驱 */
if(q!=p) q->rchild= s->lchild;/*接 *p的右子树 */
else q->lchild=s->lchild;/*接 *p的左子树 */
delete s;
}
return TRUE;
} //Delete
三,二叉排序树的查找分类
从平均查找长度分析,
设有 6个记录，其关键字序列为
(45,24,53,12,37,93)或由另一种序列构
成 (12,24,37,45,53,93)其对应的二叉排
序树,
45
53 24
12 93 37
12
53
45
37
24
93 (a) (b)
(a)树的深度为 3 (b)树的深度为 6
若每个记录的查找概率相等，为,
则树的平均查找长度为,
AsL(a)= (1+2+2+3+3+3)=
AsL(b)= (1+2+3+4+5+6)=
查找关键字与给定值的结点的过程，是从
根结点到该结点路径的过程，和给定值比
较的关键字个数等于路径长度加 1（或结点
6
1
6
1
6
14
6
1
6
21
所在层次数）。
可见，含有 n个结点的二叉排序树
的平均查找时间和树的形态有关。
若构造二叉排序树时，按关键字有序构造,
树的深度为 n。其平均查找长度为,这
是最差的情况。
若二叉排序树的形态和折半查找的判定
树相同。其平均查找长度 Log2n成正比。
2
1?n
第十章 内部排序
10.1 术语和约定
排序 (ordering)也叫分类 (sorting)，是
将一组数据按照规定顺序进行排列，其目
的是为了方便查询和处理。
按分类时分类对象存放的设备，分为内
部排序和外部排序。
排序过程中数据对象全部在内存中进行,
叫内部排序。
排序过程中数据对象并非完全在
内存中进行叫外部排序。
分类的稳定性,
对于给定数组 A，经排序处理后，满足关
系,A[1].key A[2].key … A[n].key
若在排序前存在关系,
A[i].key A[j].key ( 1 i<j n )
经排序后,A[i]和 A[j]分别被移至 A[i1]和
A[j1]，并且 i1和 j1满足关系 1 i<j n
? ? ?
? ? ?
? ?
我们称这种排序是稳定的，否则称
其为不稳定的。
影响排序性能的因素,
比较关键字的次数 — 当 关键字是字符串
时，只主要因素。
交换记录位置和移动记录的次数 — 当 记
录很大时，是主要因素。
上述两条是排序过程中进行的基本操作。
待排序记录序列可有三种存贮方式,
待排序的一组记录存放在地址连
续的一组存贮单元中。
存放在静态链表中。
地址排序，即记录存放在一组地址连续
的单元中。另设一个指示各记录存贮位
置的地址向量。排序过程中不移动记录
本身，而移动地址向量中记录的地址。
待排记录的数据类型,
#define maxsize 20
typedef int keytype;
typedef struct
{ keyType key;/*关键字 */
infoType otherinfo;
} RedType; /*记录类型 */
typedef struct
{ RedType r[maxsize+1];
int length;/*顺序表长度 */
}sqlist;
10.2 插入排序
10.2.1 直接插入排序
基本思想：将一个记录插入到已排好序的
有序表中。（个数增 1）
例，已知待排序的一组记录。
R(49),R(38),R(65),R(97),R(76),R(13),
R(27),R(49)设前 4个记录已重新排序,
{R(38),R(49),R(65),R(97)}
现要插入第 5个记录 R(76)。由 65<
76<97，则 R(76)应插入在 R(65)和
R(97)之间，而得新的有序序列,
{R(38),R(49),R(65),R(76),R(97)}
上述插入过程为一趟直接插入序列，在 i-
1个有序记录中插入第 i个为第 i个趟直接插
入排序，在找插入位置时，为防数据下标
出界，设 r[0]为监视哨，在搜索过程中，同
时后移记录。整个过程为 n-1趟插入。
实现过程,
(49) 38 65 97 76 13 27 49
i=2 (38) (38 49) 65 97 76 13 27 49
i=3 (65) (38 49 65) 97 76 13 27 49
i=4 (97) (38 49 65 97) 76 13 27 49
i=5 (76) (38 49 65 76 97) 13 27 49
i=6 (13) (13 38 49 65 76 97) 27 49
i=7 (27) (13 27 38 49 65 76 97) 49
i=8 (49) (13 27 38 49 49 65 76 97)
监视哨
算法实现,
Insertsort(L)
{ for(i=2;i<=L.length;++i)
if(LT(L.r[i].key,L.r[i-1].key))
/*<需将 L.r[i]插入有序列表 */
{ L.r[0]= L.r[i]; /*复制为哨兵 */
L.r[i]= L.r[i-1];
for(j=i-2; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]= L.r[j]; /*记录后移 */
L.r[j+1]= L.r[0]; /* 插入正确位置 */
}//Insertsort
算法分析：算法简单，容易实现,
时间复杂度为 O(n2)。
当待排序记录按关键字递增有序排
列，所需比较次数最小值，即 n-1( ),
记录不需移动。
当待排序记录是递减有序排列时，其比较
次数达最大值，即, (n+2)(n-1)/2( ),
记录移动次数,(n+4)(n-1)/2( )
?
?
n
i
i
2
?
?
n
i
i
2
?
?
?
n
i
i
2
1
10.2.2 其它插入排序
一,折半插入排序
直接插入排序，当 n很大时，效率低,
为此改进，可采用折半插入排序。
例,[1][2][3] l.r[0]
6 2 8 10 3 2 5 9
m=1 low=1 high=1
6 2 8 10 3 2 5 9
算法实现,
Binsertsort(L)
{ for(i=2;i<=L.length;++i)
{ L.r[0]= L.r[i] ;
low=1; high= i-1;
while(low<=high)
{ m= (low+high)/2;
if(LT(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]; /*插入 */
}
}//Binsertsort
算法分析：其时间复杂度仍为 O(n2)。
二,2-路插入排序
基本思想：在折半插入排序的基
础改进，增设 n各记录的辅助空间,
即设一数组 d，首先将 L.r[i]赋给 d[i]。（看
成中间位置）然后从 L.r中的第 2个记录起
依次插入到 d[1]之前或之后的有序序列中,
可将 d看成是一个循环重复，并设两个指针
first和 final，分别指示序列中的第一个记录
和最后一个记录（排序过程中序列）在 d中。
例,49 38 65 97 76 13 27 49
排序中 d的状态（形成）
i=1 (49)
first final
i=2 (49) (38)
final first
i=3 (49 65) (38)
final first
i=4 (49 65 97) (38)
final first
i=5 (49 65 76 97) (38)
final first
i=6 (49 65 76 97) (13 38)
final first
i=7 (49 65 76 97) (13 27 38)
final first
i=8 (49 49 65 76 97 13 27 38)
final first
2-路插入排序只能减少移动记录的次数，而不
能避免。
三,表插入算法
为不移动记录，可改变存贮结构
变量说明,#define size 100/*静态链表容量 */
typedef struct
{ Rcdtype rc; /*记录项 */
int next; /*指针项 */
} Slnode; /*表结点类型 */
typedef struct
{ Slnode r[size];
int length;
}链表类型（静态）
初始状态
MAXINT 49 38 65 97 76 13 27 49
1 0 - - - - - - -
key
next
MAXINT 49 38 65 97 76 13 27 49
2 0 1 - - - - - -
i=2
MAXINT 49 38 65 97 76 13 27 49
2 3 1 0 - - - - - i=3
i=4 2 3 1 4 0 - - - -
i=5 2 3 1 5 0 4 - - -
i=6 6 3 1 5 0 4 2 - -
i=7 6 3 1 5 0 4 7 2 -
i=8 6 8 1 5 0 4 7 2 3
算法分析：表插入结果得到一个有序链表，
只能顺序查找，其时间复杂度仍为 O(n2)。
10.2.3 希尔排序（缩小增量排序）
基本思想：将待排记录分成若干个
子序列，且进行直接插入排序。待整个序
列基本有序时，再对全体记录进行一次直
接插入排序。
例,49 38 65 97 76 13 27 49 55 04
一趟排序结果,
13 27 49 55 04 49 38 65 97 76
二趟排序结果,
13 04 49 38 27 49 55 65 97 76
三趟排序结果,
04 13 27 38 49 49 55 65 76 97
希尔排序的时间复杂度为 O(n3/2)。
算法实现,
shellInsert(L,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];
for(j=i-dk;
j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]= L.r[j];/*记录后移，找插入位置 */
L.r[j+dk] = L.r[0]; /*插入 */
}
}//shellInsert
shellsort (L,int dlta[],t)
/*按增量序列 dlta[0,…,t-1]*/
{ for(k=0; k<t; ++k)
shellInsert(L,dlta[k]);
/*一趟为 dlta[k]的插入序列 */
} //shellsort
最简单的排序算法,
气泡排序（冒泡）例,
x1
x2
x10
a[0]
a[1]
a[2]
a[9] ? ?
时间复杂度,
O(n2)
Ci:时间常数
算法实现,
sort(n,A)
int n; List A;
{ int x,y;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
if(A[j].key>A[j-1].key)
swap(A[j],A[j-1]);
}//sort
swap(x,y)
records x,y;
{ records temp;
temp = x;
x = y;
y = temp;
}//swap
10.3 快速排序
快速排序是基于交换排序的方法,
最简单的一种是起泡排序法。实现过程,
先将第一个记录的关键字和第二个记录的
关键字进行比较。
若 L.r[1].key>L.r[2].key，则交换两个
记录，再比较第二个记录和第三个记录的
关键字。以此类推，直至第 n-1个记录和第
n个记录的关键字进行比较。上述过程为第
一趟起泡排序，结果使得关键字最大的记
录放在最后一个记录的位置上。整
个过程进行 k(1 k n)趟起泡排序,
而判定排序过程中，起泡排序结束的
条件是, 在一趟排序过程中没有进行交换
记
录的操作, 。
算法效率：若初始序列为, 正序,,则
只
需进行一趟排序，进行 n-1次关键字间的比
较，且不移动记录，反之，若序列为, 逆
序,,则需进行 n-1趟排序，需进行
? ?
次比较。，且作相同
数量的记录移动。因此，总的时间复
杂度为 O(n2)。
例,
2/)1()1(
2
????
?
nni
ni
49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 76
49 97
初
始
一 二 三 四 五 六
算法实现,
SORT(n,A)
int n ; List A;
{ int x,y ;
for(i=1; i<=n-1; i++)
for(j=n; j>=i+1; j--)
if(A[j].key<A[j-1].key)
swap(A[j],A[j-1]);
}//SORT
swap(x,y)
records x,y;
{ records temp;
temp = x;
x = y;
y = temp;
}
快速排序,
又称分区交换排序，在排序方法中是比
较快的一种。
思想：在待排序的 n个记录中任取一个记录
（如第一个），以该记录的排序码为准，
将所有记录分成两组。第一组中各记录
的排序码都小于等于该排序码，第二组
中各记录的关键码（字）都大于该关键
码，并把该记录排在这两组中间（即该
记录最终应在的排序位置）。然后
对这两组分别重复上述过程，直至
所有记录都排到相应的位置为止。
例,{49 38 65 97 76 13 27 49}初始状态
27 38 65 97 76 13 49 49
49 38 65 97 76 13 27 49
27 38 49 97 76 13 65 49
27 38 13 97 76 49 65 49
一趟划分后,{27 38 13} 49 {76 97 65 49}
再次排序划分,
{13} 27 {38} 49 {49 65} 76 {97}
结束 结束 结束
结果,{13 27 38 49 49 65 76 97}
算法实现：一趟快速排序的具体做法是：设两个指针
low和 high，它们的初始值分别为 low(1)和 high(8)（本
例中），第一次所选记录的关键字为 pivotkey，首先从
high所据位置起向前搜索找到第一个关键字小于
pivotkey的记录和所选记录相互交换，然后从 low所指
位置向后搜索，找到第一个关键字大于 pivotkey的记录
和所选记录互相交换。重复上述（两步）直至
low=high为止。
Partition(L,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[high]= L.r[low];
}
L.r[low]= L.r[0];
return low;/*所选记录到位：返回位置 */
}//Partition
实现过程,
L.r[0] 49 38 65 97 76 13 27 49
pivotkey
记录 low=1 low=2 low=3 low high high=8
L.r[low] 27 38 13 65
key high high=7
97
high high high=6
49
算法分析,快速排序的执行时间，当
待排记录已有序的情况下，时间最
长，这时第一趟经过 n-1次比较。将第一个
记录定在他原来的位置上，并得到一个包
括 n-1个记录的子文件。第二次递归调用。
经过 n-2次比较，将其定在他原来的位置上,
并得到 n-2个记录的子文件 …… 总的比较次
数为,
{27 38 13} 49 {76 97 65 49}
?
?
?
????
1
1
2
2
)1(
2
)(
n
i
nnnin
另一个极端情况是每递归调用一
次，将记录的位置定在正好是文件
的中间，而将原文件分成两个大小
相等的子文件。这时总的比较次数为
O(n*log2n)。
快速排序是不稳定的。
10.4 堆排序
堆排序是选择排序的一种。
堆的定义,n个元素的序列 {k1,k2,…,kn}当
且仅当满足以下关系时，称为堆。
ki k2i ki k2i
ki k2i+1 ki k2i+1
若将一堆数组看成是完全二叉树，则堆
的定义是：完全二叉树中所有非终结点的值均不
大于（或不小于）其左右孩子结点的值。由此,
?
?
或
?
?
( i=1,2,…,)
2
n
若序列 {k1,k2,…,kn}是堆，则堆顶元素
（或完全二叉树的根）必为序列中 n个元
素的最小值（或最大值）。
例,{96,83,27,38,11,09}
{12,36,24,85,47,30,53,91}
对应的完全二叉树,
38
27 83
96
09 11
36
12
85
91
24
30 53 47
若输出堆顶的最小值之后，剩余
n-1个元素的序列又重建成一个堆,
堆顶为 n个元素中的次小值。如此反
复执行，可得到一个有序序列。该过程称
为堆排序。上述应解决两个问题,1.如何
建堆 2.输出堆顶元素后，如何调整构造新
的堆。
调整剩余元素成为一个新堆。
例,
38
13
27
49
97
76 65 49
97
38 27
49 76 65 49
13
a
b
38
27
49
49 76 65 97
13
38
49 49
97 76 65 27
13
c
d
自堆顶至叶子的调整过程为, 筛选, 。
从一个无序序列建堆的过程就是一
个反复, 筛选, 的过程。若将此序列看
成是一个完全二叉树，则最后一个非终端
结点是第 n/2个元素。, 筛选, 只需从第
n/2
个元素开始。
例,{49,38,65,97,76,13,27,49}
49
38 65
97 13 27 76
49
49
38 65
49 76 13 27
97
49
38 13
49 76 65 27
97
49
38 13
49 76 65 27
97
1
13
38 27
49 76 65 49
97
算法实现,
Heapsort(H)
{ for(i=H.length/2; i>0; --i)
HeapAdjust(H,i,H.length);
for(i=H; i>1; --i)
{ H.r[1] H.r[i] ;/*相互交换 */
HeapAdjust(H,1,i-1);
}
}//Heapsort
HeapAdjust(H,int s,int m)
{ 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(!LT(rc.key,H.r[j].key)) break;
H.r[s] = H.r[j]; s=j ;
}
H.r[s] = rc;
}//HeapAdjust
算法分析：堆排序适合于待排序的关键字集合较
大的情况。对 n个记录的关键字进行排序的时间
是 O(nlog2n)。
有序序列上的一个记录，应保证删
除结点后，二叉排序树的特性不变。
删除结点可有三种情况,
1.若被删除结点 *p为叶子结点，即其 pL和
pR均为空树。由于叶子结点的存在若不
破坏整株树的结构，则只需修改其父结
点的指针即可。
2.若 *p结点只有左子树 pL或只有右子树 pR，
此时只要令 pL或 pR直接成为其父结点 *f
的左子树即可。可见，也不破坏二叉排序
树的特性。
3.若 *p结点的左、右子树均不空，不能简
单处理，可有两种情况。例,
F
P
f
p
pL pR
(a)
f
F
P
C
p
c
CL Q
PR
q
S Q
L
SL
S
F
C
c
CL S
S
f
SL PR
(b) (c)
f
F
S
C
p
c
CL Q
PR
q
QL SL
(d)
二叉排序树中删除一个
结点的算法
DeleteBST(T,key)
{ if(!T) return False;
else { if(EQ(key,T->data.key))
return Delete(T);
if(LT(key,T->data.key))
return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);}
}//DeleteBST
上述三种情况的删除算法
Delete(p)/*p被删除点 */
{ if(!p->rchild) /*右子树空接其左子树 */
{q=p;p=p->lchild;free(q);}
else if(!p->lchild)/*只接其右子树 */
{ q=p;p=p->rchild;free(q);}
else
{ q=p; s=p->lchild;
while(s->rchild)
{ q=s; s=p->lchild;}
/*转左，然后向右到尽头 */
p->data= s->data;/*s指向删除结点的前驱 */
if(q!=p) q->rchild= s->lchild;/*接 *p的右子树 */
else q->lchild=s->lchild;/*接 *p的左子树 */
delete s;
}
return TRUE;
} //Delete
三,二叉排序树的查找分类
从平均查找长度分析,
设有 6个记录，其关键字序列为
(45,24,53,12,37,93)或由另一种序列构
成 (12,24,37,45,53,93)其对应的二叉排
序树,
45
53 24
12 93 37
12
53
45
37
24
93 (a) (b)
(a)树的深度为 3 (b)树的深度为 6
若每个记录的查找概率相等，为,
则树的平均查找长度为,
AsL(a)= (1+2+2+3+3+3)=
AsL(b)= (1+2+3+4+5+6)=
查找关键字与给定值的结点的过程，是从
根结点到该结点路径的过程，和给定值比
较的关键字个数等于路径长度加 1（或结点
6
1
6
1
6
14
6
1
6
21
所在层次数）。
可见，含有 n个结点的二叉排序树
的平均查找时间和树的形态有关。
若构造二叉排序树时，按关键字有序构造,
树的深度为 n。其平均查找长度为,这
是最差的情况。
若二叉排序树的形态和折半查找的判定
树相同。其平均查找长度 Log2n成正比。
2
1?n
第十章 内部排序
10.1 术语和约定
排序 (ordering)也叫分类 (sorting)，是
将一组数据按照规定顺序进行排列，其目
的是为了方便查询和处理。
按分类时分类对象存放的设备，分为内
部排序和外部排序。
排序过程中数据对象全部在内存中进行,
叫内部排序。
排序过程中数据对象并非完全在
内存中进行叫外部排序。
分类的稳定性,
对于给定数组 A，经排序处理后，满足关
系,A[1].key A[2].key … A[n].key
若在排序前存在关系,
A[i].key A[j].key ( 1 i<j n )
经排序后,A[i]和 A[j]分别被移至 A[i1]和
A[j1]，并且 i1和 j1满足关系 1 i<j n
? ? ?
? ? ?
? ?
我们称这种排序是稳定的，否则称
其为不稳定的。
影响排序性能的因素,
比较关键字的次数 — 当 关键字是字符串
时，只主要因素。
交换记录位置和移动记录的次数 — 当 记
录很大时，是主要因素。
上述两条是排序过程中进行的基本操作。
待排序记录序列可有三种存贮方式,
待排序的一组记录存放在地址连
续的一组存贮单元中。
存放在静态链表中。
地址排序，即记录存放在一组地址连续
的单元中。另设一个指示各记录存贮位
置的地址向量。排序过程中不移动记录
本身，而移动地址向量中记录的地址。
待排记录的数据类型,
#define maxsize 20
typedef int keytype;
typedef struct
{ keyType key;/*关键字 */
infoType otherinfo;
} RedType; /*记录类型 */
typedef struct
{ RedType r[maxsize+1];
int length;/*顺序表长度 */
}sqlist;
10.2 插入排序
10.2.1 直接插入排序
基本思想：将一个记录插入到已排好序的
有序表中。（个数增 1）
例，已知待排序的一组记录。
R(49),R(38),R(65),R(97),R(76),R(13),
R(27),R(49)设前 4个记录已重新排序,
{R(38),R(49),R(65),R(97)}
现要插入第 5个记录 R(76)。由 65<
76<97，则 R(76)应插入在 R(65)和
R(97)之间，而得新的有序序列,
{R(38),R(49),R(65),R(76),R(97)}
上述插入过程为一趟直接插入序列，在 i-
1个有序记录中插入第 i个为第 i个趟直接插
入排序，在找插入位置时，为防数据下标
出界，设 r[0]为监视哨，在搜索过程中，同
时后移记录。整个过程为 n-1趟插入。
实现过程,
(49) 38 65 97 76 13 27 49
i=2 (38) (38 49) 65 97 76 13 27 49
i=3 (65) (38 49 65) 97 76 13 27 49
i=4 (97) (38 49 65 97) 76 13 27 49
i=5 (76) (38 49 65 76 97) 13 27 49
i=6 (13) (13 38 49 65 76 97) 27 49
i=7 (27) (13 27 38 49 65 76 97) 49
i=8 (49) (13 27 38 49 49 65 76 97)
监视哨
算法实现,
Insertsort(L)
{ for(i=2;i<=L.length;++i)
if(LT(L.r[i].key,L.r[i-1].key))
/*<需将 L.r[i]插入有序列表 */
{ L.r[0]= L.r[i]; /*复制为哨兵 */
L.r[i]= L.r[i-1];
for(j=i-2; LT(L.r[0].key,L.r[j].key); --j)
L.r[j+1]= L.r[j]; /*记录后移 */
L.r[j+1]= L.r[0]; /* 插入正确位置 */
}//Insertsort
算法分析：算法简单，容易实现,
时间复杂度为 O(n2)。
当待排序记录按关键字递增有序排
列，所需比较次数最小值，即 n-1( ),
记录不需移动。
当待排序记录是递减有序排列时，其比较
次数达最大值，即, (n+2)(n-1)/2( ),
记录移动次数,(n+4)(n-1)/2( )
?
?
n
i
i
2
?
?
n
i
i
2
?
?
?
n
i
i
2
1
10.2.2 其它插入排序
一,折半插入排序
直接插入排序，当 n很大时，效率低,
为此改进，可采用折半插入排序。
例,[1][2][3] l.r[0]
6 2 8 10 3 2 5 9
m=1 low=1 high=1
6 2 8 10 3 2 5 9
算法实现,
Binsertsort(L)
{ for(i=2;i<=L.length;++i)
{ L.r[0]= L.r[i] ;
low=1; high= i-1;
while(low<=high)
{ m= (low+high)/2;
if(LT(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]; /*插入 */
}
}//Binsertsort
算法分析：其时间复杂度仍为 O(n2)。
二,2-路插入排序
基本思想：在折半插入排序的基
础改进，增设 n各记录的辅助空间,
即设一数组 d，首先将 L.r[i]赋给 d[i]。（看
成中间位置）然后从 L.r中的第 2个记录起
依次插入到 d[1]之前或之后的有序序列中,
可将 d看成是一个循环重复，并设两个指针
first和 final，分别指示序列中的第一个记录
和最后一个记录（排序过程中序列）在 d中。
例,49 38 65 97 76 13 27 49
排序中 d的状态（形成）
i=1 (49)
first final
i=2 (49) (38)
final first
i=3 (49 65) (38)
final first
i=4 (49 65 97) (38)
final first
i=5 (49 65 76 97) (38)
final first
i=6 (49 65 76 97) (13 38)
final first
i=7 (49 65 76 97) (13 27 38)
final first
i=8 (49 49 65 76 97 13 27 38)
final first
2-路插入排序只能减少移动记录的次数，而不
能避免。
三,表插入算法
为不移动记录，可改变存贮结构
变量说明,#define size 100/*静态链表容量 */
typedef struct
{ Rcdtype rc; /*记录项 */
int next; /*指针项 */
} Slnode; /*表结点类型 */
typedef struct
{ Slnode r[size];
int length;
}链表类型（静态）
初始状态
MAXINT 49 38 65 97 76 13 27 49
1 0 - - - - - - -
key
next
MAXINT 49 38 65 97 76 13 27 49
2 0 1 - - - - - -
i=2
MAXINT 49 38 65 97 76 13 27 49
2 3 1 0 - - - - - i=3
i=4 2 3 1 4 0 - - - -
i=5 2 3 1 5 0 4 - - -
i=6 6 3 1 5 0 4 2 - -
i=7 6 3 1 5 0 4 7 2 -
i=8 6 8 1 5 0 4 7 2 3
算法分析：表插入结果得到一个有序链表，
只能顺序查找，其时间复杂度仍为 O(n2)。
10.2.3 希尔排序（缩小增量排序）
基本思想：将待排记录分成若干个
子序列，且进行直接插入排序。待整个序
列基本有序时，再对全体记录进行一次直
接插入排序。
例,49 38 65 97 76 13 27 49 55 04
一趟排序结果,
13 27 49 55 04 49 38 65 97 76
二趟排序结果,
13 04 49 38 27 49 55 65 97 76
三趟排序结果,
04 13 27 38 49 49 55 65 76 97
希尔排序的时间复杂度为 O(n3/2)。
算法实现,
shellInsert(L,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];
for(j=i-dk;
j>0&<(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]= L.r[j];/*记录后移，找插入位置 */
L.r[j+dk] = L.r[0]; /*插入 */
}
}//shellInsert
shellsort (L,int dlta[],t)
/*按增量序列 dlta[0,…,t-1]*/
{ for(k=0; k<t; ++k)
shellInsert(L,dlta[k]);
/*一趟为 dlta[k]的插入序列 */
} //shellsort
最简单的排序算法,
气泡排序（冒泡）例,
x1
x2
x10
a[0]
a[1]
a[2]
a[9] ? ?
时间复杂度,
O(n2)
Ci:时间常数
算法实现,
sort(n,A)
int n; List A;
{ int x,y;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
if(A[j].key>A[j-1].key)
swap(A[j],A[j-1]);
}//sort
swap(x,y)
records x,y;
{ records temp;
temp = x;
x = y;
y = temp;
}//swap
10.3 快速排序
快速排序是基于交换排序的方法,
最简单的一种是起泡排序法。实现过程,
先将第一个记录的关键字和第二个记录的
关键字进行比较。
若 L.r[1].key>L.r[2].key，则交换两个
记录，再比较第二个记录和第三个记录的
关键字。以此类推，直至第 n-1个记录和第
n个记录的关键字进行比较。上述过程为第
一趟起泡排序，结果使得关键字最大的记
录放在最后一个记录的位置上。整
个过程进行 k(1 k n)趟起泡排序,
而判定排序过程中，起泡排序结束的
条件是, 在一趟排序过程中没有进行交换
记
录的操作, 。
算法效率：若初始序列为, 正序,,则
只
需进行一趟排序，进行 n-1次关键字间的比
较，且不移动记录，反之，若序列为, 逆
序,,则需进行 n-1趟排序，需进行
? ?
次比较。，且作相同
数量的记录移动。因此，总的时间复
杂度为 O(n2)。
例,
2/)1()1(
2
????
?
nni
ni
49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 76
49 97
初
始
一 二 三 四 五 六
算法实现,
SORT(n,A)
int n ; List A;
{ int x,y ;
for(i=1; i<=n-1; i++)
for(j=n; j>=i+1; j--)
if(A[j].key<A[j-1].key)
swap(A[j],A[j-1]);
}//SORT
swap(x,y)
records x,y;
{ records temp;
temp = x;
x = y;
y = temp;
}
快速排序,
又称分区交换排序，在排序方法中是比
较快的一种。
思想：在待排序的 n个记录中任取一个记录
（如第一个），以该记录的排序码为准，
将所有记录分成两组。第一组中各记录
的排序码都小于等于该排序码，第二组
中各记录的关键码（字）都大于该关键
码，并把该记录排在这两组中间（即该
记录最终应在的排序位置）。然后
对这两组分别重复上述过程，直至
所有记录都排到相应的位置为止。
例,{49 38 65 97 76 13 27 49}初始状态
27 38 65 97 76 13 49 49
49 38 65 97 76 13 27 49
27 38 49 97 76 13 65 49
27 38 13 97 76 49 65 49
一趟划分后,{27 38 13} 49 {76 97 65 49}
再次排序划分,
{13} 27 {38} 49 {49 65} 76 {97}
结束 结束 结束
结果,{13 27 38 49 49 65 76 97}
算法实现：一趟快速排序的具体做法是：设两个指针
low和 high，它们的初始值分别为 low(1)和 high(8)（本
例中），第一次所选记录的关键字为 pivotkey，首先从
high所据位置起向前搜索找到第一个关键字小于
pivotkey的记录和所选记录相互交换，然后从 low所指
位置向后搜索，找到第一个关键字大于 pivotkey的记录
和所选记录互相交换。重复上述（两步）直至
low=high为止。
Partition(L,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[high]= L.r[low];
}
L.r[low]= L.r[0];
return low;/*所选记录到位：返回位置 */
}//Partition
实现过程,
L.r[0] 49 38 65 97 76 13 27 49
pivotkey
记录 low=1 low=2 low=3 low high high=8
L.r[low] 27 38 13 65
key high high=7
97
high high high=6
49
算法分析,快速排序的执行时间，当
待排记录已有序的情况下，时间最
长，这时第一趟经过 n-1次比较。将第一个
记录定在他原来的位置上，并得到一个包
括 n-1个记录的子文件。第二次递归调用。
经过 n-2次比较，将其定在他原来的位置上,
并得到 n-2个记录的子文件 …… 总的比较次
数为,
{27 38 13} 49 {76 97 65 49}
?
?
?
????
1
1
2
2
)1(
2
)(
n
i
nnnin
另一个极端情况是每递归调用一
次，将记录的位置定在正好是文件
的中间，而将原文件分成两个大小
相等的子文件。这时总的比较次数为
O(n*log2n)。
快速排序是不稳定的。
10.4 堆排序
堆排序是选择排序的一种。
堆的定义,n个元素的序列 {k1,k2,…,kn}当
且仅当满足以下关系时，称为堆。
ki k2i ki k2i
ki k2i+1 ki k2i+1
若将一堆数组看成是完全二叉树，则堆
的定义是：完全二叉树中所有非终结点的值均不
大于（或不小于）其左右孩子结点的值。由此,
?
?
或
?
?
( i=1,2,…,)
2
n
若序列 {k1,k2,…,kn}是堆，则堆顶元素
（或完全二叉树的根）必为序列中 n个元
素的最小值（或最大值）。
例,{96,83,27,38,11,09}
{12,36,24,85,47,30,53,91}
对应的完全二叉树,
38
27 83
96
09 11
36
12
85
91
24
30 53 47
若输出堆顶的最小值之后，剩余
n-1个元素的序列又重建成一个堆,
堆顶为 n个元素中的次小值。如此反
复执行，可得到一个有序序列。该过程称
为堆排序。上述应解决两个问题,1.如何
建堆 2.输出堆顶元素后，如何调整构造新
的堆。
调整剩余元素成为一个新堆。
例,
38
13
27
49
97
76 65 49
97
38 27
49 76 65 49
13
a
b
38
27
49
49 76 65 97
13
38
49 49
97 76 65 27
13
c
d
自堆顶至叶子的调整过程为, 筛选, 。
从一个无序序列建堆的过程就是一
个反复, 筛选, 的过程。若将此序列看
成是一个完全二叉树，则最后一个非终端
结点是第 n/2个元素。, 筛选, 只需从第
n/2
个元素开始。
例,{49,38,65,97,76,13,27,49}
49
38 65
97 13 27 76
49
49
38 65
49 76 13 27
97
49
38 13
49 76 65 27
97
49
38 13
49 76 65 27
97
1
13
38 27
49 76 65 49
97
算法实现,
Heapsort(H)
{ for(i=H.length/2; i>0; --i)
HeapAdjust(H,i,H.length);
for(i=H; i>1; --i)
{ H.r[1] H.r[i] ;/*相互交换 */
HeapAdjust(H,1,i-1);
}
}//Heapsort
HeapAdjust(H,int s,int m)
{ 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(!LT(rc.key,H.r[j].key)) break;
H.r[s] = H.r[j]; s=j ;
}
H.r[s] = rc;
}//HeapAdjust
算法分析：堆排序适合于待排序的关键字集合较
大的情况。对 n个记录的关键字进行排序的时间
是 O(nlog2n)。
