第 11章 内 排 序
11.6 基数排序本章小结
11.1 排序的基本概念
11.2 插入排序
11.3 交换排序
11.4 选择排序
11.5 归并排序
11.7 各种内排序方法的比较和选择
11.1 排序的基本概念所谓 排序,就是要整理表中的记录,使之按关键字递增 (或递减 )有序排列。其确切定义如下：
输入,n 个 记 录,R0,R1,…,Rn-1,其 相 应 的 关 键 字 分 别 为
k0,k1,…,kn-1。
输出,R,R,…,R,使得 k≤k≤… ≤k(或 k≥k≥… ≥k)。
当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是 稳定的 ；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是 不稳定的 。
在排序过程中,若整个表都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为 内排序 ；反之,若排序过程中要进行数据的内、外存交换,则称之为 外排序 。
待排序的顺序表类型的类型定义如下,
typedef int KeyType; /*定义关键字类型 */
typedef struct /*记录类型 */
{
KeyType key; /*关键字项 */
InfoType data; /*其他数据项,类型为 InfoType*/
} RecType; /*排序的记录类型定义 */
11.2 插入排序插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止 。
两种插入排序方法：
(1)直接插入排序
(2)希尔排序 。
11.2.1 直接插入排序假设待排序的记录存放在数组 R[0..n-1]中,排序过程的某一中间时刻,R被划分成两个子区间 R[0..i-1]和 R[i..n-1],其中：前一个子区间是已排好序的有序区,后一个子区间则是当前未排序的部分,不妨称其为无序区 。 直接插入排序的基本操作是将当前无序区的第 1个记录 R[i]插入到有序区 R[0..i-1]中适当的位置上,使 R[0..i]变为新的有序区 。 这种方法通常称为增量法,因为它每次使有序区增加 1个记录 。
直接插入排序的算法如下：
void InsertSort(RecType R[],int n) /*对 R[0..n-1]按递增有序进行直接插入排序 */
{ int i,j; RecType temp;
for (i=1;i<n;i++)
{ temp=R[i];
j=i-1; /*从右向左在有序区 R[0..i-1]找 R[i]的插入位置 */
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; /*将关键字大于 R[i].key的记录后移 */
j--;
}
R[j+1]=temp; /*在 j+1处插入 R[i]*/
}
}
例 11.1 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。
初始关键字 9 8 7 6 5 4 3 2 1 0
i= 1 [ 8 9] 7 6 5 4 3 2 1 0
i= 2 [ 7 8 9] 6 5 4 3 2 1 0
i= 3 [ 6 7 8 9] 5 4 3 2 1 0
i= 4 [ 5 6 7 8 9] 4 3 2 1 0
i= 5 [ 4 5 6 7 8 9] 3 2 1 0
i= 6 [ 3 4 5 6 7 8 9] 2 1 0
i= 7 [ 2 3 4 5 6 7 8 9] 1 0
i= 8 [ 1 2 3 4 5 6 7 8 9] 0
i= 9 [ 0 1 2 3 4 5 6 7 8 9]
11.2.2 希尔排序希尔排序也是一种插入排序方法,实际上是一种分组插入方法 。 其基本思想是：先取定一个小于 n的整数 d1作为第一个增量,把表的全部记录分成 d1个组,所有距离为 d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量 d2(＜ d1),重复上述的分组和排序,直至所取的增量 dt=1(dt<dt-
1<… <d2<d1),即所有记录放在同一组中进行直接插入排序为止 。
希尔排序的算法如下：
void ShellSort(RecType R[],int n) /*希尔排序算法 */
{ int i,j,d;RecType temp;
d=n/2; /*d取初值 n/2*/
while (d>0)
{ for (i=d;i<n;i++) /*将 R[d..n-1]分别插入各组当前有序区 */
{ j=i-d;
while (j>=0 && R[j].key>R[j+d].key)
{ temp=R[j]; /*R[j]与 R[j+d]交换 */
R[j]=R[j+d];R[j+d]=temp;
j=j-d;
}
}
d=d/2; /*递减增量 d*/
}
}
例 11.2 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。 说明采用希尔排序方法进行排序的过程 。
9 8 7 6 5 4 3 2 1 0 初始状态 ( 连线部分为下一趟作准备 )
4 3 2 1 0 9 8 7 6 5 d =5 ( d =5 执行结果 )
0 1 2 3 4 5 6 7 8 9 d =2 ( d =2 执行结果 )
0 1 2 3 4 5 6 7 8 9 d =1 ( d =1 执行结果 )
11.3 交换排序交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止 。
两种交换排序,
(1)冒泡排序
(2)快速排序
11.3.1 冒泡排序冒泡排序的基本思想是：
通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上,漂浮,直至,水面,。
整个算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上,使得经过一趟冒泡排序后,关键字最小的记录到达最上端,接着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上 。
依次类推,一直到所有记录都有序为止 。
冒泡排序的算法如下：
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]=R[j-1];
R[j-1]=temp;
}
}
}
例 11.3 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。说明采用冒泡排序方法进行排序的过程。
初始关键字 9 8 7 6 5 4 3 2 1 0
i=0 0 9 8 7 6 5 4 3 2 1
i=1 0 1 9 8 7 6 5 4 3 2
i=2 0 1 2 9 8 7 6 5 4 3
i=3 0 1 2 3 9 8 7 6 5 4
i=4 0 1 2 3 4 9 8 7 6 5
i=5 0 1 2 3 4 5 9 8 7 6
i=6 0 1 2 3 4 5 6 9 8 7
i=7 0 1 2 3 4 5 6 7 9 8
i=8 0 1 2 3 4 5 6 7 8 9
在有些情况下,在第 i(i＜ n-1)趟时已排好序了,但仍执行后面几趟的比较 。 实际上,一旦算法中某一趟比较时不出现记录交换,说明已排好序了,就可以结束本算法 。 为此,改进冒泡排序算法如下：
void BubbleSort(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; /*中途结束算法 */
}
}
11.3.2 快速排序快速排序是由冒泡排序改进而得的,它的基本思想是：在待排序的 n个记录中任取一个记录 (通常取第一个记录 ),把该记录放入适当位置后,数据序列被此记录划分成两部分 。 所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间 (称为该记录归位 ),这个过程称作一趟快速排序 。 之后对所有的两部分分别重复上述过程,直至每部分内只有一个记录为止 。 简而言之,每趟使表的第一个元素放入适当位置,将表一分为二,对子表按递归方式继续这种划分,直至划分的子表长为 1。
void QuickSort(RecType R[],int s,int t)
/*对 R[s]至 R[t]的元素进行快速排序 */
{ int i=s,j=t; RecType temp;
if (s<t) /*区间内至少存在一个元素的情况 */
{ temp=R[s]; /*用区间的第 1个记录作为基准 */
while (i!=j) /*从两端交替向中间扫描,直至 i=j为止 */
{ while (j>i && R[j].key>temp.key) j--;
if (i<j) /*表示找到这样的 R[j],R[i],R[j]交换 */
{ R[i]=R[j]; i++; }
while (i<j && R[i].key<temp.key) i++;
if (i<j) /*表示找到这样的 R[i],R[i],R[j]交换 */
{ R[j]=R[i]; j--; }
}
R[i]=temp;
QuickSort(R,s,i-1); /*对左区间递归排序 */
QuickSort(R,i+1,t); /*对右区间递归排序 */
}
}
划分例 11.4 设待排序的表有 10个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。 说明采用快速排序方法进行排序的过程 。
初始关键字 6 8 7 9 0 1 3 2 4 5
5 4 2 3 0 1 6 9 7 8
1 4 2 3 0 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
11.4 选择排序选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕 。
两种选择排序方法：
(1)直接选择排序 (或称简单选择排序 )
(2)堆排序
11.4.1 直接选择排序直接选择排序的基本思想是：第 i趟排序开始时,当前有序区和无序区分别为 R[0..i-1]和 R[i..n-1](0≤i＜ n-1),该趟排序则是从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第 1个记录 R[i]交换,使 R[0..i]和 R[i+1..n-1]分别变为新的有序区和新的无序区 。
因为每趟排序均使有序区中增加了一个记录,且有序区中的记录关键字均不大于无序区中记录的关键字,即第 i趟排序之后 R[0..i]的所有关键字小于等于 R[i+1..n-1]中的所有关键字,所以进行 n-1趟排序之后有 R[0..n-2] 的所有关键字小于等于 R[n-
1].key,也就是说,经过 n-1趟排序之后,整个表 R[0..n-1]递增有序 。
void SelectSort(RecType R[],int n)
{ int i,j,k; RecType temp;
for (i=0;i<n-1;i++) /*做第 i趟排序 */
{ k=i;
for (j=i+1;j<n;j++) /*在 [i..n-1]中选 key最小的 R[k] */
if (R[j].key<R[k].key)
k=j; /*k记下的最小关键字所在的位置 */
if (k!=i) /*交换 R[i]和 R[k] */
{ temp=R[i]; R[i]=R[k]; R[k]=temp; }
}
}
例 11.5 设待排序的表有 10个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。说明采用直接选择排序方法进行排序的过程。
初始关键字 6 8 7 9 0 1 3 2 4 5
i=0 0 8 7 9 6 1 3 2 4 5
i=1 0 1 7 9 6 8 3 2 4 5
i=2 0 1 2 9 6 8 3 7 4 5
i=3 0 1 2 3 6 8 9 7 4 5
i=4 0 1 2 3 4 8 9 7 6 5
i=5 0 1 2 3 4 5 9 7 6 8
i=6 0 1 2 3 4 5 6 7 9 8
i=7 0 1 2 3 4 5 6 7 9 8
i=8 0 1 2 3 4 5 6 7 8 9
11.4.2 堆排序堆排序是一树形选择排序,它的特点是,在排序过程中,将
R[1..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大 (或最小 )的记录 。
堆的定义是,n个关键字序列 K1,K2,…,Kn称为 堆,当且仅当该序列满足如下性质 (简称为堆性质 )：
(1)Ki≤K2i 且 Ki≤K2i+1
或 (2)Ki≥K2i 且 Ki≥K2i+1(1≤i≤?n/2?)
满足第 (1)种情况的堆称为 小根堆,满足第 (2)种情况的堆称为大根堆 。 下面讨论的堆是 大根堆 。
堆排序的关键是构造堆,这里采用筛选算法建堆：假若完全二叉树的某一个结点 i对于它的左子树,右子树已是堆,接下来需要将 R[2i].key与 R[2i+1].key之中的最大者与 R[i].key比较,
若 R[i].key较小则交换,这有可能破坏下一级的堆 。 于是继续采用上述方法构造下一级的堆 。 直到完全二叉树中结点 i构成堆为止 。 对于任意一棵完全二叉树,从 i=?n/2?到 1,反复利用上述思想建堆 。 大者,上浮,,小者被,筛选,下去 。
其调整堆的算法 sift()如下：
void sift(RecType R[],int low,int high)
{ int i=low,j=2*i; /*R[j]是 R[i]的左孩子 */
RecType temp=R[i];
while (j<=high)
{ if (j<high && R[j].key<R[j+1].key) j++;
if (temp.key<R[j].key)
{ R[i]=R[j]; /*将 R[j]调整到双亲结点位置上 */
i=j; /*修改 i和 j值,以便继续向下筛选 */
j=2*i;
}
else break; /*筛选结束 */
}
R[i]=temp; /*被筛选结点的值放入最终位置 */
}
有了调整堆的函数,利用该函数,将已有堆中的根与最后一个叶子交换,进一步恢复堆,直到一棵树只剩一个根为止 。 实现堆排序的算法如下：
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个结点的堆 */
}
}
例 11.6 设待排序的表有 10 个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。 说明采用堆排序方法进行排序的过程 。
6
8 7
9 0
2 4
1 3
5
9
8 7
6 5
2 4
1 3
0
(a ) 初始状态 (b ) 建立的初始堆
0
8 7
6 5
2 4
1 3
8
6 7
4 5
2 0
1 3
(a ) 交换 9 与 0,输出 9 (b ) 筛选调整
0
6 7
4 5
2
1 3
(c ) 交换 8 与 0,输出 8
7
6 3
4 5
2
1 0
2
6 3
4 5 1 0
(d ) 筛选调整 (e ) 交换 7 与 2,输出 7
6
5 3
4 2 1 0
(f) 筛选调整堆排序过程：
0
5 3
4 2 1
5
4 3
0 2 1
(g ) 交换 6 与 0,输出 6 (h ) 筛选调整 (i) 交换 5 与 1,输出 5
1
4 3
0 2
4
2 3
0 1
(j) 筛选调整
1
2 3
2
3
2
0
(k ) 交换 4 与 1,输出 4 (l) 筛选调整 (m ) 交换 3 与 1,输出 3
0
2 1
2
0 1
(n ) 筛选调整
1
1
0
1
0
(o ) 交换 2 与 1,输出 2 (p ) 筛选调整 (q ) 交换 1 与 0,输出 1
0
1
0
(r ) 输出 0
11.5 归并排序归并排序是多次将两个或两个以上的有序表合并成一个新的有序表 。 最简单的归并是直接将两个有序的子表合并成一个有序的表 。
将两个有序表直接归并为一个有序表的算法 Merge(),
void Merge(RecType R[],int low,int mid,int high)
{ RecType *R1;
int i=low,j=mid+1,k=0;
/*k是 R1的下标,i,j分别为第 1,2段的下标 */
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
while (i<=mid && j<=high)
if (R[i].key<=R[j].key) /*将第 1段中的记录放入 R1中 */
{ R1[k]=R[i]; i++;k++; }
else /*将第 2段中的记录放入 R1中 */
{ R1[k]=R[j]; j++;k++; }
Merge()实现了一次归并,
while (i<=mid) /*将第 1段余下部分复制到 R1*/
{ R1[k]=R[i]; i++;k++; }
while (j<=high) /*将第 2段余下部分复制到 R1*/
{ R1[k]=R[j]; j++;k++; }
for (k=0,i=low;i<=high;k++,i++) /*将 R1复制回 R中 */
R[i]=R1[k];
}
void MergePass(RecType R[],int length,int n)
{ int i;
for (i=0;i+2*length-1<n;i=i+2*length) /*归并 length长的两相邻子表 */
Merge(R,i,i+length-1,i+2*length-1);
if (i+length-1<n) /*余下两个子表,后者长度小于 length*/
Merge(R,i,i+length-1,n-1); /*归并这两个子表 */
}
MergePass()实现了一趟归并二路归并排序算法如下：
void MergeSort(RecType R[],int n)
/*自底向上的二路归并算法 */
{
int length;
for (length=1;length<n;length=2*length)
MergePass(R,length,n);
}
例 11.7 设待排序的表有 8个记录,其关键字分别为
{18,2,20,34,12,32,6,16}。说明采用归并排序方法进行排序的过程。
初始关键字 18 2 20 34 12 32 6 16
第 1 趟归并 2 18 20 34 12 32 6 16
第 2 趟归并 2 18 20 34 6 12 16 32
第 3 趟归并 2 6 12 16 18 20 32 34
11.6 基数排序前面所讨论的排序算法均是基于关键字之间的比较来实现的,而基数排序是通过,分配,和,收集,过程来实现排序,
是一种借助于多关键字排序的思想对单关键字排序的方法 。
一般地,记录 R[i]的关键字 R[i].key是由 d位数字组成,即 kd-
1kd-2…k 0,每一个数字表示关键字的一位,其中 kd-1为最高位,k0
是最低位,每一位的值都在 0≤ki＜ r范围内,其中,r称为基数。
例如,对于二进制数 r为 2,对于十进制数 r为 10。基数排序有两种：最低位优先和最高位优先。最低位优先的过程是：
先按最低位的值对记录进行排序,在此基础上,再按次低位进行排序,依此类推。由低位向高位,每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序,直至最高位,则完成了基数排序的整个过程。
以 r为基数的最低位优先排序的过程是：假设线性表由结点序列 a0,a1,…,an-l构成,每个结点 aj的关键字由 d元组 (k,k…,k,k)
组成,其中 0≤k≤r -1(0≤j ＜ n,0≤i≤d -1)。在排序过程中,使用 r个队列 Q0,Q1,…,Qr-1。排序过程如下：
对 i=0,1,…,d-1,依次做一次,分配,和,收集,(其实就是一次稳定的排序过程 )。
分配,开始时,把 Q0,Q1,…,Qr-1各个队列置成空队列,然后依次考察线性表中的每一个结点 aj(j=0,1,…,n-1),如果 aj的关键字
k=k,就把 aj放进 Qk队列中 。
收集,把 Q0,Q1,…,Qr-1各个队列中的结点依次首尾相接,得到新的结点序列,从而组成新的线性表 。
#define MAXE 20 /*线性表中最多元素个数 */
#define MAXR 10 /*基数的最大取值 */
#define MAXD 8 /*关键字位数的最大取值 */
typedef struct node
{ char data[MAXD]; /*记录的关键字定义的字符串 */
struct node *next;
} RecType;
void RadixSort(RecType *&p,int r,int d)
/*p为待排序序列链表指针,r为基数,d为关键字位数 */
{ RecType *head[MAXR],*tail[MAXR],*t;
/*定义各链队的首尾指针 */
int i,j,k;
for (i=d-1;i>=0;i--) /*从低位到高位做 d趟排序 */
{ for (j=0;j<r;j++) /*初始化各链队首,尾指针 */
head[j]=tail[j]=NULL;
while (p!=NULL) /*对于原链表中每个结点循环 */
{ k=p->data[i]-'0'; /*找第 k个链队 */
if (head[k]==NULL)
/*进行分配,即采用尾插法建立单链表 */
{ head[k]=p; tail[k]=p; }
else
{ tail[k]->next=p; tail[k]=p; }
p=p->next; /*取下一个待排序的元素 */
}
分配
p=NULL;
for (j=0;j<r;j++) /*对于每一个链队循环进行收集 */
if (head[j]!=NULL)
{ if (p==NULL)
{ p=head[j];
t=tail[j];
}
else
{ t->next=head[j];
t=tail[j];
}
}
t->next=NULL;
/*最后一个结点的 next域置 NULL*/
}
}
收集例 11.8 设待排序的表有 10个记录,其关键字分别为
{75,23,98,44,57,12,29,64,38,82}。说明采用基数排序方法进行排序的过程。
初始关键字 75 23 98 44 57 12 29 64 38 82
按个数排序 12 82 23 44 64 75 57 98 38 29
按十位排序 12 23 29 38 44 57 64 75 82 98
p 75 23 98 44 57 12 29 64 38 82 ∧ （ a ）初始状态
h e a d [ 0 ] h e a d [ 1 ] h e a d [ 2 ] h e a d [ 3 ] h e a d [ 4 ] h e a d [ 5 ] h e a d [ 6 ] h e a d [ 7 ] h e a d [ 8 ] h e a d [ 9 ]
ta il [ 0 ] ta il [ 1 ] ta il [ 2 ] ta il [ 3 ] ta il [ 4 ] ta il [ 5 ] ta il [ 6 ] ta il [ 7 ] ta il [ 8 ] ta il [ 9 ]
12
82
∧
23
∧
75
∧
57
∧
29
∧
44
64
∧
98
38
∧
链队头指针链队尾指针
（ b ）按个位分配之后
p 12 82 23 44 64 75 57 98 38 29 ∧ （ c ）按个位收集之后
h e a d [ 0 ] h e a d [ 1 ] h e a d [ 2 ] h e a d [ 3 ] h e a d [ 4 ] h e a d [ 5 ] h e a d [ 6 ] h e a d [ 7 ] h e a d [ 8 ] h e a d [ 9 ]
ta il [ 0 ] ta il [ 1 ] ta il [ 2 ] ta il [ 3 ] ta il [ 4 ] ta il [ 5 ] ta il [ 6 ] ta il [ 7 ] ta il [ 8 ] ta il [ 9 ]
12
∧
29
∧
23
38
∧
75
∧
98
∧
链队头指针链队尾指针
（ d ）按十位分配之后
p 12 23 29 38 44 57 64 75 82 98 ∧ （ e ）按十位收集之后
44
∧
57
∧
64
∧
82
∧
11.7 各种内排序方法的比较和选择本章介绍了多种排序方法,将这些排序方法总结为表 11.1。
通常可按平均时间将排序方法分为三类：
（ 1） 平方阶 O(n2)排序,一般称为简单排序,例如直接插入,直接选择和冒泡排序；
（ 2） 线性对数阶 O(nlog2n)排序,如快速,堆和归并排序；
（ 3）线性阶 O(n)排序，如基数排序。
排序方法时间复杂度空间复杂度 稳定性 复杂性平均情况 最坏情况 最好情况直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单希尔排序 O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单快速排序 O(nlog2n) O(n
2) O(nlog
2n) O(nlog2n) 不稳定 较复杂直接选择排序 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+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂本章小结本章基本学习要点如下：
(1) 理解排序的基本概念,包括排序的稳定性,内排序和外排序之间的差异 。
(2) 重点掌握插入排序算法,包括直接插入排序和希尔排序的过程和算法实现 。
(3) 重点掌握交换排序算法,包括冒泡排序和快速排序的过程和算法实现 。
(4) 重点掌握选择排序算法,包括直接选择排序和堆排序的过程和算法实现 。
(5) 掌握归并排序的过程和算法实现 。
(6) 掌握基数排序的过程和算法实现 。
(7) 灵活运用各种排序算法解决一些综合应用问题。
练习教材中 p287习题 2,3和 5。
上机实习题教材中 p287题 4和 10。
11.6 基数排序本章小结
11.1 排序的基本概念
11.2 插入排序
11.3 交换排序
11.4 选择排序
11.5 归并排序
11.7 各种内排序方法的比较和选择
11.1 排序的基本概念所谓 排序,就是要整理表中的记录,使之按关键字递增 (或递减 )有序排列。其确切定义如下：
输入,n 个 记 录,R0,R1,…,Rn-1,其 相 应 的 关 键 字 分 别 为
k0,k1,…,kn-1。
输出,R,R,…,R,使得 k≤k≤… ≤k(或 k≥k≥… ≥k)。
当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是 稳定的 ；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是 不稳定的 。
在排序过程中,若整个表都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为 内排序 ；反之,若排序过程中要进行数据的内、外存交换,则称之为 外排序 。
待排序的顺序表类型的类型定义如下,
typedef int KeyType; /*定义关键字类型 */
typedef struct /*记录类型 */
{
KeyType key; /*关键字项 */
InfoType data; /*其他数据项,类型为 InfoType*/
} RecType; /*排序的记录类型定义 */
11.2 插入排序插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止 。
两种插入排序方法：
(1)直接插入排序
(2)希尔排序 。
11.2.1 直接插入排序假设待排序的记录存放在数组 R[0..n-1]中,排序过程的某一中间时刻,R被划分成两个子区间 R[0..i-1]和 R[i..n-1],其中：前一个子区间是已排好序的有序区,后一个子区间则是当前未排序的部分,不妨称其为无序区 。 直接插入排序的基本操作是将当前无序区的第 1个记录 R[i]插入到有序区 R[0..i-1]中适当的位置上,使 R[0..i]变为新的有序区 。 这种方法通常称为增量法,因为它每次使有序区增加 1个记录 。
直接插入排序的算法如下：
void InsertSort(RecType R[],int n) /*对 R[0..n-1]按递增有序进行直接插入排序 */
{ int i,j; RecType temp;
for (i=1;i<n;i++)
{ temp=R[i];
j=i-1; /*从右向左在有序区 R[0..i-1]找 R[i]的插入位置 */
while (j>=0 && temp.key<R[j].key)
{ R[j+1]=R[j]; /*将关键字大于 R[i].key的记录后移 */
j--;
}
R[j+1]=temp; /*在 j+1处插入 R[i]*/
}
}
例 11.1 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。
初始关键字 9 8 7 6 5 4 3 2 1 0
i= 1 [ 8 9] 7 6 5 4 3 2 1 0
i= 2 [ 7 8 9] 6 5 4 3 2 1 0
i= 3 [ 6 7 8 9] 5 4 3 2 1 0
i= 4 [ 5 6 7 8 9] 4 3 2 1 0
i= 5 [ 4 5 6 7 8 9] 3 2 1 0
i= 6 [ 3 4 5 6 7 8 9] 2 1 0
i= 7 [ 2 3 4 5 6 7 8 9] 1 0
i= 8 [ 1 2 3 4 5 6 7 8 9] 0
i= 9 [ 0 1 2 3 4 5 6 7 8 9]
11.2.2 希尔排序希尔排序也是一种插入排序方法,实际上是一种分组插入方法 。 其基本思想是：先取定一个小于 n的整数 d1作为第一个增量,把表的全部记录分成 d1个组,所有距离为 d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量 d2(＜ d1),重复上述的分组和排序,直至所取的增量 dt=1(dt<dt-
1<… <d2<d1),即所有记录放在同一组中进行直接插入排序为止 。
希尔排序的算法如下：
void ShellSort(RecType R[],int n) /*希尔排序算法 */
{ int i,j,d;RecType temp;
d=n/2; /*d取初值 n/2*/
while (d>0)
{ for (i=d;i<n;i++) /*将 R[d..n-1]分别插入各组当前有序区 */
{ j=i-d;
while (j>=0 && R[j].key>R[j+d].key)
{ temp=R[j]; /*R[j]与 R[j+d]交换 */
R[j]=R[j+d];R[j+d]=temp;
j=j-d;
}
}
d=d/2; /*递减增量 d*/
}
}
例 11.2 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。 说明采用希尔排序方法进行排序的过程 。
9 8 7 6 5 4 3 2 1 0 初始状态 ( 连线部分为下一趟作准备 )
4 3 2 1 0 9 8 7 6 5 d =5 ( d =5 执行结果 )
0 1 2 3 4 5 6 7 8 9 d =2 ( d =2 执行结果 )
0 1 2 3 4 5 6 7 8 9 d =1 ( d =1 执行结果 )
11.3 交换排序交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止 。
两种交换排序,
(1)冒泡排序
(2)快速排序
11.3.1 冒泡排序冒泡排序的基本思想是：
通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上,漂浮,直至,水面,。
整个算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上,使得经过一趟冒泡排序后,关键字最小的记录到达最上端,接着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上 。
依次类推,一直到所有记录都有序为止 。
冒泡排序的算法如下：
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]=R[j-1];
R[j-1]=temp;
}
}
}
例 11.3 设待排序的表有 10个记录,其关键字分别为
{9,8,7,6,5,4,3,2,1,0}。说明采用冒泡排序方法进行排序的过程。
初始关键字 9 8 7 6 5 4 3 2 1 0
i=0 0 9 8 7 6 5 4 3 2 1
i=1 0 1 9 8 7 6 5 4 3 2
i=2 0 1 2 9 8 7 6 5 4 3
i=3 0 1 2 3 9 8 7 6 5 4
i=4 0 1 2 3 4 9 8 7 6 5
i=5 0 1 2 3 4 5 9 8 7 6
i=6 0 1 2 3 4 5 6 9 8 7
i=7 0 1 2 3 4 5 6 7 9 8
i=8 0 1 2 3 4 5 6 7 8 9
在有些情况下,在第 i(i＜ n-1)趟时已排好序了,但仍执行后面几趟的比较 。 实际上,一旦算法中某一趟比较时不出现记录交换,说明已排好序了,就可以结束本算法 。 为此,改进冒泡排序算法如下：
void BubbleSort(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; /*中途结束算法 */
}
}
11.3.2 快速排序快速排序是由冒泡排序改进而得的,它的基本思想是：在待排序的 n个记录中任取一个记录 (通常取第一个记录 ),把该记录放入适当位置后,数据序列被此记录划分成两部分 。 所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间 (称为该记录归位 ),这个过程称作一趟快速排序 。 之后对所有的两部分分别重复上述过程,直至每部分内只有一个记录为止 。 简而言之,每趟使表的第一个元素放入适当位置,将表一分为二,对子表按递归方式继续这种划分,直至划分的子表长为 1。
void QuickSort(RecType R[],int s,int t)
/*对 R[s]至 R[t]的元素进行快速排序 */
{ int i=s,j=t; RecType temp;
if (s<t) /*区间内至少存在一个元素的情况 */
{ temp=R[s]; /*用区间的第 1个记录作为基准 */
while (i!=j) /*从两端交替向中间扫描,直至 i=j为止 */
{ while (j>i && R[j].key>temp.key) j--;
if (i<j) /*表示找到这样的 R[j],R[i],R[j]交换 */
{ R[i]=R[j]; i++; }
while (i<j && R[i].key<temp.key) i++;
if (i<j) /*表示找到这样的 R[i],R[i],R[j]交换 */
{ R[j]=R[i]; j--; }
}
R[i]=temp;
QuickSort(R,s,i-1); /*对左区间递归排序 */
QuickSort(R,i+1,t); /*对右区间递归排序 */
}
}
划分例 11.4 设待排序的表有 10个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。 说明采用快速排序方法进行排序的过程 。
初始关键字 6 8 7 9 0 1 3 2 4 5
5 4 2 3 0 1 6 9 7 8
1 4 2 3 0 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 9 7 8
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
11.4 选择排序选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕 。
两种选择排序方法：
(1)直接选择排序 (或称简单选择排序 )
(2)堆排序
11.4.1 直接选择排序直接选择排序的基本思想是：第 i趟排序开始时,当前有序区和无序区分别为 R[0..i-1]和 R[i..n-1](0≤i＜ n-1),该趟排序则是从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第 1个记录 R[i]交换,使 R[0..i]和 R[i+1..n-1]分别变为新的有序区和新的无序区 。
因为每趟排序均使有序区中增加了一个记录,且有序区中的记录关键字均不大于无序区中记录的关键字,即第 i趟排序之后 R[0..i]的所有关键字小于等于 R[i+1..n-1]中的所有关键字,所以进行 n-1趟排序之后有 R[0..n-2] 的所有关键字小于等于 R[n-
1].key,也就是说,经过 n-1趟排序之后,整个表 R[0..n-1]递增有序 。
void SelectSort(RecType R[],int n)
{ int i,j,k; RecType temp;
for (i=0;i<n-1;i++) /*做第 i趟排序 */
{ k=i;
for (j=i+1;j<n;j++) /*在 [i..n-1]中选 key最小的 R[k] */
if (R[j].key<R[k].key)
k=j; /*k记下的最小关键字所在的位置 */
if (k!=i) /*交换 R[i]和 R[k] */
{ temp=R[i]; R[i]=R[k]; R[k]=temp; }
}
}
例 11.5 设待排序的表有 10个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。说明采用直接选择排序方法进行排序的过程。
初始关键字 6 8 7 9 0 1 3 2 4 5
i=0 0 8 7 9 6 1 3 2 4 5
i=1 0 1 7 9 6 8 3 2 4 5
i=2 0 1 2 9 6 8 3 7 4 5
i=3 0 1 2 3 6 8 9 7 4 5
i=4 0 1 2 3 4 8 9 7 6 5
i=5 0 1 2 3 4 5 9 7 6 8
i=6 0 1 2 3 4 5 6 7 9 8
i=7 0 1 2 3 4 5 6 7 9 8
i=8 0 1 2 3 4 5 6 7 8 9
11.4.2 堆排序堆排序是一树形选择排序,它的特点是,在排序过程中,将
R[1..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大 (或最小 )的记录 。
堆的定义是,n个关键字序列 K1,K2,…,Kn称为 堆,当且仅当该序列满足如下性质 (简称为堆性质 )：
(1)Ki≤K2i 且 Ki≤K2i+1
或 (2)Ki≥K2i 且 Ki≥K2i+1(1≤i≤?n/2?)
满足第 (1)种情况的堆称为 小根堆,满足第 (2)种情况的堆称为大根堆 。 下面讨论的堆是 大根堆 。
堆排序的关键是构造堆,这里采用筛选算法建堆：假若完全二叉树的某一个结点 i对于它的左子树,右子树已是堆,接下来需要将 R[2i].key与 R[2i+1].key之中的最大者与 R[i].key比较,
若 R[i].key较小则交换,这有可能破坏下一级的堆 。 于是继续采用上述方法构造下一级的堆 。 直到完全二叉树中结点 i构成堆为止 。 对于任意一棵完全二叉树,从 i=?n/2?到 1,反复利用上述思想建堆 。 大者,上浮,,小者被,筛选,下去 。
其调整堆的算法 sift()如下：
void sift(RecType R[],int low,int high)
{ int i=low,j=2*i; /*R[j]是 R[i]的左孩子 */
RecType temp=R[i];
while (j<=high)
{ if (j<high && R[j].key<R[j+1].key) j++;
if (temp.key<R[j].key)
{ R[i]=R[j]; /*将 R[j]调整到双亲结点位置上 */
i=j; /*修改 i和 j值,以便继续向下筛选 */
j=2*i;
}
else break; /*筛选结束 */
}
R[i]=temp; /*被筛选结点的值放入最终位置 */
}
有了调整堆的函数,利用该函数,将已有堆中的根与最后一个叶子交换,进一步恢复堆,直到一棵树只剩一个根为止 。 实现堆排序的算法如下：
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个结点的堆 */
}
}
例 11.6 设待排序的表有 10 个记录,其关键字分别为
{6,8,7,9,0,1,3,2,4,5}。 说明采用堆排序方法进行排序的过程 。
6
8 7
9 0
2 4
1 3
5
9
8 7
6 5
2 4
1 3
0
(a ) 初始状态 (b ) 建立的初始堆
0
8 7
6 5
2 4
1 3
8
6 7
4 5
2 0
1 3
(a ) 交换 9 与 0,输出 9 (b ) 筛选调整
0
6 7
4 5
2
1 3
(c ) 交换 8 与 0,输出 8
7
6 3
4 5
2
1 0
2
6 3
4 5 1 0
(d ) 筛选调整 (e ) 交换 7 与 2,输出 7
6
5 3
4 2 1 0
(f) 筛选调整堆排序过程：
0
5 3
4 2 1
5
4 3
0 2 1
(g ) 交换 6 与 0,输出 6 (h ) 筛选调整 (i) 交换 5 与 1,输出 5
1
4 3
0 2
4
2 3
0 1
(j) 筛选调整
1
2 3
2
3
2
0
(k ) 交换 4 与 1,输出 4 (l) 筛选调整 (m ) 交换 3 与 1,输出 3
0
2 1
2
0 1
(n ) 筛选调整
1
1
0
1
0
(o ) 交换 2 与 1,输出 2 (p ) 筛选调整 (q ) 交换 1 与 0,输出 1
0
1
0
(r ) 输出 0
11.5 归并排序归并排序是多次将两个或两个以上的有序表合并成一个新的有序表 。 最简单的归并是直接将两个有序的子表合并成一个有序的表 。
将两个有序表直接归并为一个有序表的算法 Merge(),
void Merge(RecType R[],int low,int mid,int high)
{ RecType *R1;
int i=low,j=mid+1,k=0;
/*k是 R1的下标,i,j分别为第 1,2段的下标 */
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
while (i<=mid && j<=high)
if (R[i].key<=R[j].key) /*将第 1段中的记录放入 R1中 */
{ R1[k]=R[i]; i++;k++; }
else /*将第 2段中的记录放入 R1中 */
{ R1[k]=R[j]; j++;k++; }
Merge()实现了一次归并,
while (i<=mid) /*将第 1段余下部分复制到 R1*/
{ R1[k]=R[i]; i++;k++; }
while (j<=high) /*将第 2段余下部分复制到 R1*/
{ R1[k]=R[j]; j++;k++; }
for (k=0,i=low;i<=high;k++,i++) /*将 R1复制回 R中 */
R[i]=R1[k];
}
void MergePass(RecType R[],int length,int n)
{ int i;
for (i=0;i+2*length-1<n;i=i+2*length) /*归并 length长的两相邻子表 */
Merge(R,i,i+length-1,i+2*length-1);
if (i+length-1<n) /*余下两个子表,后者长度小于 length*/
Merge(R,i,i+length-1,n-1); /*归并这两个子表 */
}
MergePass()实现了一趟归并二路归并排序算法如下：
void MergeSort(RecType R[],int n)
/*自底向上的二路归并算法 */
{
int length;
for (length=1;length<n;length=2*length)
MergePass(R,length,n);
}
例 11.7 设待排序的表有 8个记录,其关键字分别为
{18,2,20,34,12,32,6,16}。说明采用归并排序方法进行排序的过程。
初始关键字 18 2 20 34 12 32 6 16
第 1 趟归并 2 18 20 34 12 32 6 16
第 2 趟归并 2 18 20 34 6 12 16 32
第 3 趟归并 2 6 12 16 18 20 32 34
11.6 基数排序前面所讨论的排序算法均是基于关键字之间的比较来实现的,而基数排序是通过,分配,和,收集,过程来实现排序,
是一种借助于多关键字排序的思想对单关键字排序的方法 。
一般地,记录 R[i]的关键字 R[i].key是由 d位数字组成,即 kd-
1kd-2…k 0,每一个数字表示关键字的一位,其中 kd-1为最高位,k0
是最低位,每一位的值都在 0≤ki＜ r范围内,其中,r称为基数。
例如,对于二进制数 r为 2,对于十进制数 r为 10。基数排序有两种：最低位优先和最高位优先。最低位优先的过程是：
先按最低位的值对记录进行排序,在此基础上,再按次低位进行排序,依此类推。由低位向高位,每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序,直至最高位,则完成了基数排序的整个过程。
以 r为基数的最低位优先排序的过程是：假设线性表由结点序列 a0,a1,…,an-l构成,每个结点 aj的关键字由 d元组 (k,k…,k,k)
组成,其中 0≤k≤r -1(0≤j ＜ n,0≤i≤d -1)。在排序过程中,使用 r个队列 Q0,Q1,…,Qr-1。排序过程如下：
对 i=0,1,…,d-1,依次做一次,分配,和,收集,(其实就是一次稳定的排序过程 )。
分配,开始时,把 Q0,Q1,…,Qr-1各个队列置成空队列,然后依次考察线性表中的每一个结点 aj(j=0,1,…,n-1),如果 aj的关键字
k=k,就把 aj放进 Qk队列中 。
收集,把 Q0,Q1,…,Qr-1各个队列中的结点依次首尾相接,得到新的结点序列,从而组成新的线性表 。
#define MAXE 20 /*线性表中最多元素个数 */
#define MAXR 10 /*基数的最大取值 */
#define MAXD 8 /*关键字位数的最大取值 */
typedef struct node
{ char data[MAXD]; /*记录的关键字定义的字符串 */
struct node *next;
} RecType;
void RadixSort(RecType *&p,int r,int d)
/*p为待排序序列链表指针,r为基数,d为关键字位数 */
{ RecType *head[MAXR],*tail[MAXR],*t;
/*定义各链队的首尾指针 */
int i,j,k;
for (i=d-1;i>=0;i--) /*从低位到高位做 d趟排序 */
{ for (j=0;j<r;j++) /*初始化各链队首,尾指针 */
head[j]=tail[j]=NULL;
while (p!=NULL) /*对于原链表中每个结点循环 */
{ k=p->data[i]-'0'; /*找第 k个链队 */
if (head[k]==NULL)
/*进行分配,即采用尾插法建立单链表 */
{ head[k]=p; tail[k]=p; }
else
{ tail[k]->next=p; tail[k]=p; }
p=p->next; /*取下一个待排序的元素 */
}
分配
p=NULL;
for (j=0;j<r;j++) /*对于每一个链队循环进行收集 */
if (head[j]!=NULL)
{ if (p==NULL)
{ p=head[j];
t=tail[j];
}
else
{ t->next=head[j];
t=tail[j];
}
}
t->next=NULL;
/*最后一个结点的 next域置 NULL*/
}
}
收集例 11.8 设待排序的表有 10个记录,其关键字分别为
{75,23,98,44,57,12,29,64,38,82}。说明采用基数排序方法进行排序的过程。
初始关键字 75 23 98 44 57 12 29 64 38 82
按个数排序 12 82 23 44 64 75 57 98 38 29
按十位排序 12 23 29 38 44 57 64 75 82 98
p 75 23 98 44 57 12 29 64 38 82 ∧ （ a ）初始状态
h e a d [ 0 ] h e a d [ 1 ] h e a d [ 2 ] h e a d [ 3 ] h e a d [ 4 ] h e a d [ 5 ] h e a d [ 6 ] h e a d [ 7 ] h e a d [ 8 ] h e a d [ 9 ]
ta il [ 0 ] ta il [ 1 ] ta il [ 2 ] ta il [ 3 ] ta il [ 4 ] ta il [ 5 ] ta il [ 6 ] ta il [ 7 ] ta il [ 8 ] ta il [ 9 ]
12
82
∧
23
∧
75
∧
57
∧
29
∧
44
64
∧
98
38
∧
链队头指针链队尾指针
（ b ）按个位分配之后
p 12 82 23 44 64 75 57 98 38 29 ∧ （ c ）按个位收集之后
h e a d [ 0 ] h e a d [ 1 ] h e a d [ 2 ] h e a d [ 3 ] h e a d [ 4 ] h e a d [ 5 ] h e a d [ 6 ] h e a d [ 7 ] h e a d [ 8 ] h e a d [ 9 ]
ta il [ 0 ] ta il [ 1 ] ta il [ 2 ] ta il [ 3 ] ta il [ 4 ] ta il [ 5 ] ta il [ 6 ] ta il [ 7 ] ta il [ 8 ] ta il [ 9 ]
12
∧
29
∧
23
38
∧
75
∧
98
∧
链队头指针链队尾指针
（ d ）按十位分配之后
p 12 23 29 38 44 57 64 75 82 98 ∧ （ e ）按十位收集之后
44
∧
57
∧
64
∧
82
∧
11.7 各种内排序方法的比较和选择本章介绍了多种排序方法,将这些排序方法总结为表 11.1。
通常可按平均时间将排序方法分为三类：
（ 1） 平方阶 O(n2)排序,一般称为简单排序,例如直接插入,直接选择和冒泡排序；
（ 2） 线性对数阶 O(nlog2n)排序,如快速,堆和归并排序；
（ 3）线性阶 O(n)排序，如基数排序。
排序方法时间复杂度空间复杂度 稳定性 复杂性平均情况 最坏情况 最好情况直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单希尔排序 O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单快速排序 O(nlog2n) O(n
2) O(nlog
2n) O(nlog2n) 不稳定 较复杂直接选择排序 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+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂本章小结本章基本学习要点如下：
(1) 理解排序的基本概念,包括排序的稳定性,内排序和外排序之间的差异 。
(2) 重点掌握插入排序算法,包括直接插入排序和希尔排序的过程和算法实现 。
(3) 重点掌握交换排序算法,包括冒泡排序和快速排序的过程和算法实现 。
(4) 重点掌握选择排序算法,包括直接选择排序和堆排序的过程和算法实现 。
(5) 掌握归并排序的过程和算法实现 。
(6) 掌握基数排序的过程和算法实现 。
(7) 灵活运用各种排序算法解决一些综合应用问题。
练习教材中 p287习题 2,3和 5。
上机实习题教材中 p287题 4和 10。
