内容提要
? 7.1 排序的基本概念
? 7.2 内部排序
? 内部排序的分类
? 插入排序
? 交换排序
? 选择排序
? 合并排序
? 计数排序
? 基数排序
? 内部排序方法比较
? 7.3 外部排序
1、排 序,按照结点中的某项值对集合中结点进
行升序或降序的排列。
2、关 键 字,排序时参照的数据项，有主次之分
3、稳 定 性,如果排序操作使等值结点的相对位置 (
主要是指前后关系 )保持不变，则排序是
稳定的，否则是不稳定的。
4、内部排序,排序序列放在内存中
5、外部排序,需要对外存进行访问
7.1 排序的基本概念
7.1 内排序
1、内部排序的分类
I.按照时间复杂度来分 (排序的结点数量为 n)
(1).简单的排序方法,O(n2)
(2).先进的排序方法,O(nlog2n)
(3).基数排序,O(dxn)
II.按照排序过程中所依据的原则来分
(1).插入排序
(2).交换排序
(3).选择排序
(4).合并排序
III.按照是否改变结点的物理位置来分
(1).物理重排
(2).不改变结点位置的排序，包括：链地址法，利用辅助地
址表排序，计数排序等
算法思想,
(1)已知顺序存储的待排序序列 a1,a2,a3,….,a n
(2)假设 Ak是 a1,a2,..,ak序列，并已经有序，则待
排序列是 Akak+1,…,a n,排序的基本操作是：将
ak+1有序插入到 Ak中，这样循环往复，直到排
序完毕。
(3)一开始 Ak={a1}
(4)将 ak+1有序插入到 Ak中的操作：先找到插入
位置，然后移动数据留出空间，再将 ak+1插入
内排序 (cont’d)
2、插入排序 (1) 直接插入排序
void insort(RECTYPE r[],int n) //升序排序
{RECTYPE temp; int i,j,low,hight,m;
for(i=1;i<n;i++) //r[0]已经有序，从 r[1]开始
{ if(r[i].key<r[i-1].key) //准备插入
{ low=0; high=i-1; //折半查找法，寻找插入位置
while(low<=high)
{ m=(low+high)/2;
if(r[m].key>r[i].key)high=m-1;
else if(r[m].key<r[i].key) low=m+1;
else {high=m; break;}
}//while
//r[i]应该插在 high+1的位置上
temp=r[i]; //保存 r[i]，同时留出移动数据的空间
j=i-1; while(j>=high+1){r[j+1]=r[j]; j--; }; //移动数据
r[high+1]=temp; //插入
}// if }//for
}
内排序 (cont’d)
2、插入排序 (1) 直接插入排序
内排序 (cont’d)
2、插入排序 (2) 改进插入排序之一：二路插入
49 38 65 97 76 13 27 49
Final
49
First
38
First
65
Final
97
Final
9776
Final
13
First
2713
First
97766549
Final
算法思想,
先将待排纪录分成若干子列分别用直
接插入法排序，再对全体纪录用直接插
入法排序。
理论根据：直接排序序列 越短越好,源
序列的排序度越好效率越高。
内排序 (cont’d)
2、插入排序 (3) 改进插入排序之二：希尔排序
内排序 (cont’d)
2、插入排序 (3) 改进插入排序之二：希尔排序
49 38 65 97 76 13 27 49 55 4
一趟排序结果：
13 27 49 55 4 49 38 65 97 76
二趟排序结果：
13 4 49 38 27 49 55 65 97 76
三趟排序结果：
4 13 27 38 49 49 55 65 76 97
算法思想,
直接插入排序需要移动结点数据，如果结点数
据比较大，需要移动的内存就比较多。如果建
立一个辅助地址表，每个单元都指向一个结点，
然后对地址表按照结点关键字进行排序，将会
减少数据移动的数量
内排序 (cont’d)
2、插入排序 (4) 辅助地址表的插入排序
void insort(RECTYPE r[],int n,int t[])
{//t是辅助地址表，每个单元是 r中结点的下标
int temp,i,j;
for(i=0;i<n;i++) t[i]=i; //初始化辅助地址表
for(i=1;i<n;i++)
{if(r[t[i]].key<r[t[i-1]].key)
{ j=i-1; temp=t[i];
while(j>=0&&r[t[j]].key>r[temp].key)
{ t[j+1]=t[j]; j--; } //寻找插入位置的同时，移动数据
t[j+1]=temp; //插入
}
}
}
内排序 (cont’d)
2、插入排序 (4) 辅助地址表的插入排序
算法思想,
(1)对于 n个结点的序列来说，扫描辅助地址表 t的 n个单元，如果发现
t[i]=i，则 r[i]不需要调整，如果 t[i]!=i，不能直接将 r[i]复制成 r[t[i]]，
需要进入第 2步
(2)首先，执行 temp=r[i]，保存 r[i],将 i赋值给 j，
循环执行下面的操作：
k=t[j],这时 r[j]可以覆盖，覆盖成 r[k]，同时令 t[k]=k,j＝ k。
这样循环直到遇到 t[j]＝ i为止。这时跳出循环，执行 r[j]=temp; 并
转到 (1)
内排序 (cont’d)
2、插入排序 利用辅助地址表的对结点进行物理重排
35 14 12 42 26 50 31 17
0 1 2 3 4 5 6 7
2 1 7 4 6 0 3 5
0 1 2 3 4 5 6 7
35
void rearrange(RECTYPE r[],int t[],int n)
{ RECTYPE temp; int i,j,k;
for(i=0;i<=n;i++)
if(t[i]!=i)
{ temp=r[i]; j=i;
while(t[j]!=i)
{k=t[j]; r[j]=r[k]; t[j]=j; j=k;}
r[j]=temp;
t[j]=j;
}
}
内排序 (cont’d)
2、插入排序
利用辅助地址表的对结点进行物理重排
void bubblesort(RECTYPE r[],int n)
{ RECTYPE temp; int i,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(r[j].key>r[j+1].key)
{temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
}
}
时间复杂度, O(n2)
内排序 (cont’d)
3、交换排序
(1) 直接交换排序 (冒泡排序 )
(1) 直接交换排序 (冒泡排序 )
改进思想,
(1) 一旦某趟起泡过程中没有发生冒泡，就结束算法
(2) 记下没有发生冒泡的区间 k..n-i，下次冒泡终点就
是 k-1
(3) 利用传送代替交换，当遇到 ak需要上冒时，并不
交换数据，而是将后序比它小的数据向前移动，直
到遇到 aj比 ak大为止，然后将 ak放到 aj的前面。
(4) 可以交替地从左向右上冒和从右向左下沉
内排序 (cont’d)
3、交换排序
void bubblesort(RECTYPE r[],int n)
{ int x=0,y=n-1,t=1,d=1,j,s;
/*[x..y]是起泡区间,d是起泡方向,s是待起泡地结点关键字的值，
t既表明是否发生冒泡操作，也标识着下一趟起泡的终点 */
RECTYPE temp;
while(t)//t标识是否发生了冒泡
{ j=x; s=r[j].key; temp=r[j]; t=0;
while(j*d<y*d)
{ if(s*d<r[j+d].key*d) //移动结点,并记下下一次起泡的终点
{r[j]=r[j+d]; j+=d; t=j;}
else {r[j]=temp; j+=d; s=r[j].key; temp=r[j];}
}//while
r[j]=temp;
y=x; x=t; d=-d; //改变起泡的区间和方向
}//while t
}
(2)改进地冒泡排序算法
内排序 (cont’d)
3、交换排序
算法思想,
通过一趟排序将待排纪录分成上下两个子列，
上子列大于下子列。再对两个子列继续排序。
理论依据,排序序列越短越好，源序列的排序
度越好效率越高。
(3) 快速排序
内排序 (cont’d)
3、交换排序
49 38 65 97 76 13 27 4949
low highlow highlow high high
27
low
6513 97
high
49pivotkey
内排序 (cont’d)
3、交换排序
void part(RECTYPE r[],int low,int high,int *pivotloc)
{ RECTYPE temp; int pivotkey;
pivotkey=r[low].key; temp=r[low];
while(high!=low) //完成分割
{
while(high>low&&r[high].key>=pivotkey)high--; //下行
if(high>low) //下行时遇到了比 pivotkey小的结点
{r[low]=r[high]; low++;}
while(high>low&&r[low].key<=pivotkey) low++;//上行
if(high>low)//上行时遇到了比 pivotkey大的结点
{ r[high]=r[low]; high--;}
}//while
r[low]=temp;
*pivotloc=low;
}
quicksort(RECTYPE r[],int low,int high)
int k;
if(low<high)
{ part(r,low,high,&k);
quicksort(r,low,k-1);
quicksort(r,k+1,high);
}
}
快速排序算法
内排序 (cont’d)
4、选择排序
void selectsort(RECTYPE r[],int n)
{
RECTYPE temp;
int i,j,k;
for(i=1;i<n;i++)
{ k=i;
for(j=i+1;j<=n;j++)
if(r[j].key<r[k].key) k=j;
if(k!=i)
{ temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}//for
}
(1) 直接选择排序
内排序 (cont’d)
4、选择排序 (2) 树型选择排序
也叫锦标赛排序
13
38 13
38 65 27
49 38 27
13
76 13 4965 97
两两比较 [n/2]次选出最小值
内排序 (cont’d)
4、选择排序 (2) 树型选择排序
先将最小值由顶向下去掉，最底层换上 Maxint
再比较 log2n次。
重复这一过程 n-1次得到全排序序列
时间复杂性 O(nlog2n)
空间开销大
38
38 65 27
49 38 2776 4965 97
76
27
27
内排序 (cont’d)
5、合并排序（归并排序）
将两个或两个以上有序表组合成一个新的有序表
叫做 归并排序 。
2路归并
将一个序列看成是 n个由单个元素组成的子序列，
每个子序列都是有序的长度为 1。
再将这些子序列两两合并，得到 [n/2]个长度为 2的
有序子序列。
继续两两合并，直到合并成一个长度为 n的有序序
列。每次合并，子序列的长度都成倍增长。
归并排序需要开辟一个辅助空间存放中间状态和最
后的结果。
内排序 (cont’d)
5、合并排序（归并排序）
49 38 65 97 76 13 27 49
38 49 65 97 13 76 27 49
38 49 65 97 13 27 49 76
13 27 38 49 49 65 76 97
时间复杂性 O(nlogn)
内排序 (cont’d)
5、合并排序（归并排序）
void segmentmerge(RECTYPE r1[],RECTYPE r2[],int p,int m,int n)
{/*r1[p..m]和 r1[m+1..n]是相邻的有序段，本算法将它们合并后存放
到 r2[p..n]中 */
int i,j,k;
i=p; k=p; j=m+1;
while(i<=m&&j<=n)
if(r1[i].key<=r1[j].key)r2[k++]=r1[i++];
else r2[k++]=r1[j++];
while(i<=m) r2[k++]=r1[i++]; //将剩余的部分续接到 r2中
while(j<=n) r2[k++]=r1[j++];
}
passmerge(RECTYPE r1[],RECTYPE r2[],int len,int n)
len是本趟合并的有序子段的长度,n是待排序列的长度,本算法完
成一次长度为 len的归并 */
k;
k=1;
e(k+2*len-1<=n) //还有至少 2个长度是 len子段没有合并
{ segmentmerge(r1,r2,k,k+len-1,k+2*len-1);
k+=2*len;
}
if(k+len-1<n)//最后一对有序段，最后一段长度不足 len的情况
segment(r1,r2,k,k+len-1,n);
else //只剩下一个有序段
while(k<=n) {r2[k]=r1[k]; k++; }
}
mergesort(RE r[],RECTYPE r2[],int n)//归并排序
{ int len;
len=1;//子段长度初始化为 1
while(len<n)
{ assmerge(r,r2,len,n); len*=2;
passmerge(r2,r,len,n); len*=2;
}
}
算法思想,
(1)设置一个数组，存放待排序列各结点的
计数信息。结点的计数信息是指比该结点
小或大的其他结点的个数。
(2)一开始所有的结点计数都为 1，针对每
个结点，遍历其他结点，当遇到比当前结
点大或小的结点时，结点计数增 1。
(3)结点的计数即是结点的排序序号
内排序 (cont’d)
6、计数排序
void countsort(RECTYPE r[],int count[],int n)
{
int i,j;
for(i=0;i<n;i++) count[i]=1;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(r[i].key<=r[j].key)count[j]++;
else count[i]++;
}
内排序 (cont’d)
6、计数排序
内排序 (cont’d)
(7)基数排序 ----多关键字排序
例、扑克牌排序，规则：
?2< ?3< ··<?K<?A
?2< ?3< ··<?K<?A
? 2<?3< ··<?K<?A
? 2<?3< ··<?K<?A
?<?<?<?法：
1、先排花色
2、先排面值
内排序 (cont’d)
7、基数排序 ----多关键字排序
利用多关键码排序的思想处理单关键码的排序问题。
假定有一个 n个对象序列 {V0,V1,…V n-1}，且每个对象
Vi都含有 d个关键码 (Ki1,Ki2,…,K id)。如果对于序列中任
意两个对象 Vi和 Vj都满足：
(Ki1,Ki2,…,K id)<=(Kj1,Kj2,…,K jd)或
(Ki1,Ki2,…,K id)>=(Kj1,Kj2,…,K jd)
则称序列对关键码 (K1,K2,…,K d)有序，其中,K1称
为最高位关键码,Kd称为最低位关键码。
ab<ac ba>ab
内排序 (cont’d)
7、基数排序 ----多关键字排序
实现多关键码排序有两种常用的方法，一种是最高位
优先法 (MSD,Most Significant Digit first)，一种是最低位
优先法 (LSD,Least Significant Digit first)。
MSD通常是一个递归过程：首先根据最高位关键码 K1
进行排序，得到若干个子序列，每个子序列中的对象都
具有相同的关键码 K1 。然后分别对每个子序列根据关键
码 K2进行排序，按 K2值的不同，再分成若干个更小的子
序列，每个子序列中的对象具有相同的 K1, K2值。这样
重复，直到对关键码 Kd完成排序为止。
LSD做法是：首先根据最低关键码 Kd对所有对象进行
一趟排序，然后根据次低关键码 Kd-1对上一趟排序结果再
进行一次排序并保证排序结果对 Kd有序。这样重复，直
到根据 K1进行最后一趟排序为止。
LSD也可以用于单关键码的排序，所要做的
是将单关键码分解成多关键码。
算法思想,
链式基数排序的过程就是 d(是多关键码的个数 )
次分配和收集操作的过程。整个操作过程需要辅
设多个队列，根据关键码的取值范围确定辅设队
列的个数。比如，对 0--999之间的整数进行排序，
每个数具有 3个关键码，就是各数位上的数，每个
关键码的取值范围都是 0-9，因此需要设置 10个队
列。队列的用途是完成排序对象的分配与收集。
这个 10就是基数，他决定了队列的个数。
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
614 738 921 485 637 101 215 530 790 306
530 790 921 101 614 485 215 306 637 738
第一次分配和收集
790
530
101
921 614 306 738
215
485 637
队列号
0 1 2 3 4 5 6 7 8 9
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
101 306 614 215 921 530 637 738 485 790
第二次分配和收集
306
101
215
614 921 485
738
637
530
790
队列号
0 1 2 3 4 5 6 7 8 9
530 790 921 101 614 485 215 306 637 738
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
101 215 306 485 530 614 637 738 790 921
第三次分配和收集
101 215 485 637614306 530 790738 921
队列号
0 1 2 3 4 5 6 7 8 9
101 306 614 215 921 530 637 738 485 790
#define RADIX 26 //定义最大基数
#define D 10 //定义关键字的位数
void radixsort(RECTYPE r[],int d,int radix,int n)
{/*d是关键字的位数,radix是基数,n是待排序列的长度,r
是静态链表结构,RECTYPE包含 next域 */
int h[RADIX],t[RADIX]; //用于分配和收集的队列
int p,i,j,k;
char ch[D+1],str[80];
for(i=0;i<n;i++)r[i].next=i+1; //初始化静态链表
r[n].next=0;
内排序 (cont’d)
for(j=d-1;j>=0;j--)//d次分配和收集
{ for(i=0;i<radix;i++) h[i]=t[i]=0; //清空队列
p=r[0].next;
while(p) //遍历静态链表，开始分配
{sprintf(str,"%%0%dd",d);
sprintf(ch,str,r[p].key); i=ch[j]-'0';
if(h[i]!=0) r[t[i]].next=p; //入队
else h[i] =p;
t[i]=p; p=r[p].next;
}//while
i=0;//开始收集
while(!h[i]) i++; //找到队号最小的不空队列
r[0].next=h[i]; k=i+1;
while(k<=radix-1)
{ if(h[k]) { r[t[i]].next=h[k]; i=k;}
k++; }//while
r[t[i]].next=0; }//for
}
链式基数排序算法
内排序 (cont’d)
8、内部排序方法的比较
排序方法
平均时间复
杂度
最坏情况 最好情况 辅助空间 稳定性
插入排序 O(n
2
) O(n
2
) O(n ) O(1 ) Y es
选择排序 O(n
2
) O(n
2
) O(n
2
) O(1 ) No
直接交换 O(n
2
) O(n
2
) O(n ) O(1 ) Y es
快速排序 O(n lo g
2
n) O(n
2
) O(n lo g
2
n) O(n lo g
2
n) No
堆排序 O(n lo g
2
n) O(n lo g
2
n) O(n lo g
2
n) O(1 ) No
归并排序 O(n lo g
2
n) O(n lo g
2
n) O(n lo g
2
n) O(n ) Y es
基数排序 O( dxn) O( dxn) O( dxn) O(n ) Y es
n个结点排序的最佳时间复杂度 O(nlog2n)
7.3 外排序
外部排序,指对大型文件的排序，由于文件中结点
数据比较大，不可能将所有数据都放入内
存。
外部排序的类型,归并排序，归并段放在文件中，
归并结果放在另一文件中。
影响外部排序的因素,起始归并段的大小以及一次
归并几段。
只需了解其
基本思想
,数据结构,
第七章 排序
? 7.1 排序的基本概念
? 7.2 内部排序
? 内部排序的分类
? 插入排序
? 交换排序
? 选择排序
? 合并排序
? 计数排序
? 基数排序
? 内部排序方法比较
? 7.3 外部排序
1、排 序,按照结点中的某项值对集合中结点进
行升序或降序的排列。
2、关 键 字,排序时参照的数据项，有主次之分
3、稳 定 性,如果排序操作使等值结点的相对位置 (
主要是指前后关系 )保持不变，则排序是
稳定的，否则是不稳定的。
4、内部排序,排序序列放在内存中
5、外部排序,需要对外存进行访问
7.1 排序的基本概念
7.1 内排序
1、内部排序的分类
I.按照时间复杂度来分 (排序的结点数量为 n)
(1).简单的排序方法,O(n2)
(2).先进的排序方法,O(nlog2n)
(3).基数排序,O(dxn)
II.按照排序过程中所依据的原则来分
(1).插入排序
(2).交换排序
(3).选择排序
(4).合并排序
III.按照是否改变结点的物理位置来分
(1).物理重排
(2).不改变结点位置的排序，包括：链地址法，利用辅助地
址表排序，计数排序等
算法思想,
(1)已知顺序存储的待排序序列 a1,a2,a3,….,a n
(2)假设 Ak是 a1,a2,..,ak序列，并已经有序，则待
排序列是 Akak+1,…,a n,排序的基本操作是：将
ak+1有序插入到 Ak中，这样循环往复，直到排
序完毕。
(3)一开始 Ak={a1}
(4)将 ak+1有序插入到 Ak中的操作：先找到插入
位置，然后移动数据留出空间，再将 ak+1插入
内排序 (cont’d)
2、插入排序 (1) 直接插入排序
void insort(RECTYPE r[],int n) //升序排序
{RECTYPE temp; int i,j,low,hight,m;
for(i=1;i<n;i++) //r[0]已经有序，从 r[1]开始
{ if(r[i].key<r[i-1].key) //准备插入
{ low=0; high=i-1; //折半查找法，寻找插入位置
while(low<=high)
{ m=(low+high)/2;
if(r[m].key>r[i].key)high=m-1;
else if(r[m].key<r[i].key) low=m+1;
else {high=m; break;}
}//while
//r[i]应该插在 high+1的位置上
temp=r[i]; //保存 r[i]，同时留出移动数据的空间
j=i-1; while(j>=high+1){r[j+1]=r[j]; j--; }; //移动数据
r[high+1]=temp; //插入
}// if }//for
}
内排序 (cont’d)
2、插入排序 (1) 直接插入排序
内排序 (cont’d)
2、插入排序 (2) 改进插入排序之一：二路插入
49 38 65 97 76 13 27 49
Final
49
First
38
First
65
Final
97
Final
9776
Final
13
First
2713
First
97766549
Final
算法思想,
先将待排纪录分成若干子列分别用直
接插入法排序，再对全体纪录用直接插
入法排序。
理论根据：直接排序序列 越短越好,源
序列的排序度越好效率越高。
内排序 (cont’d)
2、插入排序 (3) 改进插入排序之二：希尔排序
内排序 (cont’d)
2、插入排序 (3) 改进插入排序之二：希尔排序
49 38 65 97 76 13 27 49 55 4
一趟排序结果：
13 27 49 55 4 49 38 65 97 76
二趟排序结果：
13 4 49 38 27 49 55 65 97 76
三趟排序结果：
4 13 27 38 49 49 55 65 76 97
算法思想,
直接插入排序需要移动结点数据，如果结点数
据比较大，需要移动的内存就比较多。如果建
立一个辅助地址表，每个单元都指向一个结点，
然后对地址表按照结点关键字进行排序，将会
减少数据移动的数量
内排序 (cont’d)
2、插入排序 (4) 辅助地址表的插入排序
void insort(RECTYPE r[],int n,int t[])
{//t是辅助地址表，每个单元是 r中结点的下标
int temp,i,j;
for(i=0;i<n;i++) t[i]=i; //初始化辅助地址表
for(i=1;i<n;i++)
{if(r[t[i]].key<r[t[i-1]].key)
{ j=i-1; temp=t[i];
while(j>=0&&r[t[j]].key>r[temp].key)
{ t[j+1]=t[j]; j--; } //寻找插入位置的同时，移动数据
t[j+1]=temp; //插入
}
}
}
内排序 (cont’d)
2、插入排序 (4) 辅助地址表的插入排序
算法思想,
(1)对于 n个结点的序列来说，扫描辅助地址表 t的 n个单元，如果发现
t[i]=i，则 r[i]不需要调整，如果 t[i]!=i，不能直接将 r[i]复制成 r[t[i]]，
需要进入第 2步
(2)首先，执行 temp=r[i]，保存 r[i],将 i赋值给 j，
循环执行下面的操作：
k=t[j],这时 r[j]可以覆盖，覆盖成 r[k]，同时令 t[k]=k,j＝ k。
这样循环直到遇到 t[j]＝ i为止。这时跳出循环，执行 r[j]=temp; 并
转到 (1)
内排序 (cont’d)
2、插入排序 利用辅助地址表的对结点进行物理重排
35 14 12 42 26 50 31 17
0 1 2 3 4 5 6 7
2 1 7 4 6 0 3 5
0 1 2 3 4 5 6 7
35
void rearrange(RECTYPE r[],int t[],int n)
{ RECTYPE temp; int i,j,k;
for(i=0;i<=n;i++)
if(t[i]!=i)
{ temp=r[i]; j=i;
while(t[j]!=i)
{k=t[j]; r[j]=r[k]; t[j]=j; j=k;}
r[j]=temp;
t[j]=j;
}
}
内排序 (cont’d)
2、插入排序
利用辅助地址表的对结点进行物理重排
void bubblesort(RECTYPE r[],int n)
{ RECTYPE temp; int i,j;
for(i=1;i<n;i++)
for(j=0;j<n-i;j++)
if(r[j].key>r[j+1].key)
{temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
}
}
时间复杂度, O(n2)
内排序 (cont’d)
3、交换排序
(1) 直接交换排序 (冒泡排序 )
(1) 直接交换排序 (冒泡排序 )
改进思想,
(1) 一旦某趟起泡过程中没有发生冒泡，就结束算法
(2) 记下没有发生冒泡的区间 k..n-i，下次冒泡终点就
是 k-1
(3) 利用传送代替交换，当遇到 ak需要上冒时，并不
交换数据，而是将后序比它小的数据向前移动，直
到遇到 aj比 ak大为止，然后将 ak放到 aj的前面。
(4) 可以交替地从左向右上冒和从右向左下沉
内排序 (cont’d)
3、交换排序
void bubblesort(RECTYPE r[],int n)
{ int x=0,y=n-1,t=1,d=1,j,s;
/*[x..y]是起泡区间,d是起泡方向,s是待起泡地结点关键字的值，
t既表明是否发生冒泡操作，也标识着下一趟起泡的终点 */
RECTYPE temp;
while(t)//t标识是否发生了冒泡
{ j=x; s=r[j].key; temp=r[j]; t=0;
while(j*d<y*d)
{ if(s*d<r[j+d].key*d) //移动结点,并记下下一次起泡的终点
{r[j]=r[j+d]; j+=d; t=j;}
else {r[j]=temp; j+=d; s=r[j].key; temp=r[j];}
}//while
r[j]=temp;
y=x; x=t; d=-d; //改变起泡的区间和方向
}//while t
}
(2)改进地冒泡排序算法
内排序 (cont’d)
3、交换排序
算法思想,
通过一趟排序将待排纪录分成上下两个子列，
上子列大于下子列。再对两个子列继续排序。
理论依据,排序序列越短越好，源序列的排序
度越好效率越高。
(3) 快速排序
内排序 (cont’d)
3、交换排序
49 38 65 97 76 13 27 4949
low highlow highlow high high
27
low
6513 97
high
49pivotkey
内排序 (cont’d)
3、交换排序
void part(RECTYPE r[],int low,int high,int *pivotloc)
{ RECTYPE temp; int pivotkey;
pivotkey=r[low].key; temp=r[low];
while(high!=low) //完成分割
{
while(high>low&&r[high].key>=pivotkey)high--; //下行
if(high>low) //下行时遇到了比 pivotkey小的结点
{r[low]=r[high]; low++;}
while(high>low&&r[low].key<=pivotkey) low++;//上行
if(high>low)//上行时遇到了比 pivotkey大的结点
{ r[high]=r[low]; high--;}
}//while
r[low]=temp;
*pivotloc=low;
}
quicksort(RECTYPE r[],int low,int high)
int k;
if(low<high)
{ part(r,low,high,&k);
quicksort(r,low,k-1);
quicksort(r,k+1,high);
}
}
快速排序算法
内排序 (cont’d)
4、选择排序
void selectsort(RECTYPE r[],int n)
{
RECTYPE temp;
int i,j,k;
for(i=1;i<n;i++)
{ k=i;
for(j=i+1;j<=n;j++)
if(r[j].key<r[k].key) k=j;
if(k!=i)
{ temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}//for
}
(1) 直接选择排序
内排序 (cont’d)
4、选择排序 (2) 树型选择排序
也叫锦标赛排序
13
38 13
38 65 27
49 38 27
13
76 13 4965 97
两两比较 [n/2]次选出最小值
内排序 (cont’d)
4、选择排序 (2) 树型选择排序
先将最小值由顶向下去掉，最底层换上 Maxint
再比较 log2n次。
重复这一过程 n-1次得到全排序序列
时间复杂性 O(nlog2n)
空间开销大
38
38 65 27
49 38 2776 4965 97
76
27
27
内排序 (cont’d)
5、合并排序（归并排序）
将两个或两个以上有序表组合成一个新的有序表
叫做 归并排序 。
2路归并
将一个序列看成是 n个由单个元素组成的子序列，
每个子序列都是有序的长度为 1。
再将这些子序列两两合并，得到 [n/2]个长度为 2的
有序子序列。
继续两两合并，直到合并成一个长度为 n的有序序
列。每次合并，子序列的长度都成倍增长。
归并排序需要开辟一个辅助空间存放中间状态和最
后的结果。
内排序 (cont’d)
5、合并排序（归并排序）
49 38 65 97 76 13 27 49
38 49 65 97 13 76 27 49
38 49 65 97 13 27 49 76
13 27 38 49 49 65 76 97
时间复杂性 O(nlogn)
内排序 (cont’d)
5、合并排序（归并排序）
void segmentmerge(RECTYPE r1[],RECTYPE r2[],int p,int m,int n)
{/*r1[p..m]和 r1[m+1..n]是相邻的有序段，本算法将它们合并后存放
到 r2[p..n]中 */
int i,j,k;
i=p; k=p; j=m+1;
while(i<=m&&j<=n)
if(r1[i].key<=r1[j].key)r2[k++]=r1[i++];
else r2[k++]=r1[j++];
while(i<=m) r2[k++]=r1[i++]; //将剩余的部分续接到 r2中
while(j<=n) r2[k++]=r1[j++];
}
passmerge(RECTYPE r1[],RECTYPE r2[],int len,int n)
len是本趟合并的有序子段的长度,n是待排序列的长度,本算法完
成一次长度为 len的归并 */
k;
k=1;
e(k+2*len-1<=n) //还有至少 2个长度是 len子段没有合并
{ segmentmerge(r1,r2,k,k+len-1,k+2*len-1);
k+=2*len;
}
if(k+len-1<n)//最后一对有序段，最后一段长度不足 len的情况
segment(r1,r2,k,k+len-1,n);
else //只剩下一个有序段
while(k<=n) {r2[k]=r1[k]; k++; }
}
mergesort(RE r[],RECTYPE r2[],int n)//归并排序
{ int len;
len=1;//子段长度初始化为 1
while(len<n)
{ assmerge(r,r2,len,n); len*=2;
passmerge(r2,r,len,n); len*=2;
}
}
算法思想,
(1)设置一个数组，存放待排序列各结点的
计数信息。结点的计数信息是指比该结点
小或大的其他结点的个数。
(2)一开始所有的结点计数都为 1，针对每
个结点，遍历其他结点，当遇到比当前结
点大或小的结点时，结点计数增 1。
(3)结点的计数即是结点的排序序号
内排序 (cont’d)
6、计数排序
void countsort(RECTYPE r[],int count[],int n)
{
int i,j;
for(i=0;i<n;i++) count[i]=1;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(r[i].key<=r[j].key)count[j]++;
else count[i]++;
}
内排序 (cont’d)
6、计数排序
内排序 (cont’d)
(7)基数排序 ----多关键字排序
例、扑克牌排序，规则：
?2< ?3< ··<?K<?A
?2< ?3< ··<?K<?A
? 2<?3< ··<?K<?A
? 2<?3< ··<?K<?A
?<?<?<?法：
1、先排花色
2、先排面值
内排序 (cont’d)
7、基数排序 ----多关键字排序
利用多关键码排序的思想处理单关键码的排序问题。
假定有一个 n个对象序列 {V0,V1,…V n-1}，且每个对象
Vi都含有 d个关键码 (Ki1,Ki2,…,K id)。如果对于序列中任
意两个对象 Vi和 Vj都满足：
(Ki1,Ki2,…,K id)<=(Kj1,Kj2,…,K jd)或
(Ki1,Ki2,…,K id)>=(Kj1,Kj2,…,K jd)
则称序列对关键码 (K1,K2,…,K d)有序，其中,K1称
为最高位关键码,Kd称为最低位关键码。
ab<ac ba>ab
内排序 (cont’d)
7、基数排序 ----多关键字排序
实现多关键码排序有两种常用的方法，一种是最高位
优先法 (MSD,Most Significant Digit first)，一种是最低位
优先法 (LSD,Least Significant Digit first)。
MSD通常是一个递归过程：首先根据最高位关键码 K1
进行排序，得到若干个子序列，每个子序列中的对象都
具有相同的关键码 K1 。然后分别对每个子序列根据关键
码 K2进行排序，按 K2值的不同，再分成若干个更小的子
序列，每个子序列中的对象具有相同的 K1, K2值。这样
重复，直到对关键码 Kd完成排序为止。
LSD做法是：首先根据最低关键码 Kd对所有对象进行
一趟排序，然后根据次低关键码 Kd-1对上一趟排序结果再
进行一次排序并保证排序结果对 Kd有序。这样重复，直
到根据 K1进行最后一趟排序为止。
LSD也可以用于单关键码的排序，所要做的
是将单关键码分解成多关键码。
算法思想,
链式基数排序的过程就是 d(是多关键码的个数 )
次分配和收集操作的过程。整个操作过程需要辅
设多个队列，根据关键码的取值范围确定辅设队
列的个数。比如，对 0--999之间的整数进行排序，
每个数具有 3个关键码，就是各数位上的数，每个
关键码的取值范围都是 0-9，因此需要设置 10个队
列。队列的用途是完成排序对象的分配与收集。
这个 10就是基数，他决定了队列的个数。
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
614 738 921 485 637 101 215 530 790 306
530 790 921 101 614 485 215 306 637 738
第一次分配和收集
790
530
101
921 614 306 738
215
485 637
队列号
0 1 2 3 4 5 6 7 8 9
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
101 306 614 215 921 530 637 738 485 790
第二次分配和收集
306
101
215
614 921 485
738
637
530
790
队列号
0 1 2 3 4 5 6 7 8 9
530 790 921 101 614 485 215 306 637 738
内排序 (cont’d)
7、基数排序 ----多关键字排序
链式基数排序
101 215 306 485 530 614 637 738 790 921
第三次分配和收集
101 215 485 637614306 530 790738 921
队列号
0 1 2 3 4 5 6 7 8 9
101 306 614 215 921 530 637 738 485 790
#define RADIX 26 //定义最大基数
#define D 10 //定义关键字的位数
void radixsort(RECTYPE r[],int d,int radix,int n)
{/*d是关键字的位数,radix是基数,n是待排序列的长度,r
是静态链表结构,RECTYPE包含 next域 */
int h[RADIX],t[RADIX]; //用于分配和收集的队列
int p,i,j,k;
char ch[D+1],str[80];
for(i=0;i<n;i++)r[i].next=i+1; //初始化静态链表
r[n].next=0;
内排序 (cont’d)
for(j=d-1;j>=0;j--)//d次分配和收集
{ for(i=0;i<radix;i++) h[i]=t[i]=0; //清空队列
p=r[0].next;
while(p) //遍历静态链表，开始分配
{sprintf(str,"%%0%dd",d);
sprintf(ch,str,r[p].key); i=ch[j]-'0';
if(h[i]!=0) r[t[i]].next=p; //入队
else h[i] =p;
t[i]=p; p=r[p].next;
}//while
i=0;//开始收集
while(!h[i]) i++; //找到队号最小的不空队列
r[0].next=h[i]; k=i+1;
while(k<=radix-1)
{ if(h[k]) { r[t[i]].next=h[k]; i=k;}
k++; }//while
r[t[i]].next=0; }//for
}
链式基数排序算法
内排序 (cont’d)
8、内部排序方法的比较
排序方法
平均时间复
杂度
最坏情况 最好情况 辅助空间 稳定性
插入排序 O(n
2
) O(n
2
) O(n ) O(1 ) Y es
选择排序 O(n
2
) O(n
2
) O(n
2
) O(1 ) No
直接交换 O(n
2
) O(n
2
) O(n ) O(1 ) Y es
快速排序 O(n lo g
2
n) O(n
2
) O(n lo g
2
n) O(n lo g
2
n) No
堆排序 O(n lo g
2
n) O(n lo g
2
n) O(n lo g
2
n) O(1 ) No
归并排序 O(n lo g
2
n) O(n lo g
2
n) O(n lo g
2
n) O(n ) Y es
基数排序 O( dxn) O( dxn) O( dxn) O(n ) Y es
n个结点排序的最佳时间复杂度 O(nlog2n)
7.3 外排序
外部排序,指对大型文件的排序，由于文件中结点
数据比较大，不可能将所有数据都放入内
存。
外部排序的类型,归并排序，归并段放在文件中，
归并结果放在另一文件中。
影响外部排序的因素,起始归并段的大小以及一次
归并几段。
只需了解其
基本思想
,数据结构,
第七章 排序
