第十章 内部排序
基本概念
插入排序
快速排序
选择排序
归并排序
基数排序
10.1 基本概念设含有 n个记录的文件 {R1,R2,...,Rn},其相应的关键字为 {K1,K2,...,Kn},将记录按关键字值非递减 (或非递增 )顺序排列的过程,称为 排序 。
对所有的 Ki=Kj (i≠j),若排序前 Ri领先于 Rj,排序后
Ri仍领先于 Rj,则称该排序方法是 稳定的,反之,称为 不稳定 的 。
稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置 （ 即领先关系 ） 是否变化 。
10.1 基本概念内部排序,待排序文件的全部记录存放在内存进行的排序,称为内部排序 。
外部排序,排序过程中需要进行内外存数据交换的排序,称为外部排序 。
10.1 基本概念内排序分类按排序过程依据的原则分为：插入排序交换排序选择排序归并排序计数排序按排序过程所需的工作量分：简单排序 O(n2)
先进排序 O(nlogn)
基数排序 O(d,n)
10.2 插入排序一,直接插入排序 (最简单的排序方法 ）
⒈ 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置 (有序子文件记录数增 1)
例如：已有待排序文件为,38,65,49,76,97
首先将文件的第一个记录,视为有序文件,然后从第二个记录开始,直到最后一个记录,依次将他们插入到有序文件的合适位置 。
10.2 插入排序
⒉ 直接插入排序算法
void InsertSort(SqList &L)；
{for( i=2;i<= n;i++)
{ r[0]=r[i];
j=i-1; /*r[1]～ r[i-1]为有序子文件 */
while (r[0].key＜ r[j].key)
{ r[j+1]=r[j]; j=j-1 }; /*确定插入位置并移动 */
r[j+1]=r[0];
}
}//strainsort
10.2 插入排序
⒊ 算法分析
⑴ 空间上,只需 i,j两个整型变量和一个记录的辅助空间 r[0],r[0]
作为,监视哨,,控制待插入元素相对于有序子文件为最小时
WHILE循环的结束,同时也用于暂存待插入元素 。
⑵ 时间上,只包含比较关键字和移动记录两种操作 。
① 比较次数,
1/.当待初始文件按关键字递增有序 (正序 )时：
a.对每个记录只进行一次比较,整个排序过程共
n进行了 ∑1=n-1次比较 (最少 )；
i=2
b.每个记录都要进行 r[i]移到 r[0]和 r[0]移到 r[j+1]两次移动,
因此共移动 2(n-1)次 (最少 )。
10.2 插入排序
2/,当待排序文件按关键字非递增有序 (逆序 )时
① 记录 r[i](i=2,3,...n)均要和前 i-1个记录及 r[0]进行比较,整个排序过程共进行了
n∑ i=(n+2)(n-1)/2次比较 (最多 )；
i=2
② 移动记录次数：每个记录都要进行 r[i]移动到 r[0]和 r[0]移动到 r[j+1]两次移动,另外当 r[i].key＜ r[j].key时,还将 r[j]移动到 r[j+1],所以,当初始文件为正序时,移动记录次数最少为 2（ n-1） 次,当初始文件为逆序时移动记录次数最多为
n
∑ (i-1)+2(n-1)=(n+4)(n-1)/2次 (最多 )。
i=2
10.2 插入排序
⑶ 结论
1/,直接插入排序的效率与待排文件的关键字排列有关；
2/,直接插入排序的时间复杂度为 O(n2)；
3/,直接插入排序是稳定的 (这一点由过程中 WHILE语句的条件,＜,保证的 )。 void InsertSort(SqList &L)；
{for( i=2;i<= n;i++)
{ r[0]=r[i];
j=i-1;
while (r[0].key＜ r[j].key)
{ r[j+1]=r[j]; j=j-1; };
r[j+1]=r[0];}
}//strainsort
10.2 插入排序二,折半插入排序由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，
从而可减少比较次数。
10.2 插入排序
Void BInsertSort( SqList &L)；
{ for ( i=2;i<=L.length;i++)
{low=1； high=i-1 ； L.r[0]=L.r[i]；
while (low≤high)
{m=(low+high)/2；
if (L.r[i],key＜ L.r[m],key) //＜确保稳定，若改为 ≤，则不稳定
high＝ｍ -1;
else low=m+1； }
for ( k=i-1;k>= high+1;k--) L.r[k+1]=L.r[k]；
L.r[high+1]=L.r[0];}
}//BInsertSort
移动次数未变，故仍为 O(n2)
10.2 插入排序三,希尔排序 （ Shell`s Methool） (又称为缩小增量排序 )
⒈ 基本思想,分割成若干个较小的子文件,对各个子文件分别进行直接插入排序,当文件达到基本有序时,再对整个文件进行一次直接插入排序 。
⒉ 依据,⑴ 若待排序文件 "基本有序 ",即文件中具有特性：
r[i].key＜ Max {r[j ]} 1≤j＜ i的记录数较少,
则文件中大多数记录都不需要进行插入 。
⑵ 基本有序时,直接插入排序效率可以提高,接近于 O(n)。
10.2 插入排序
⒊ 例,设初始关键字为,49 38 65 97 76 13 27 49' 55 04
第一趟以步长为 5分割为 5个子文件,(R1,R6) (R2,R7) (R3,R8)
(R4,R6) (R5,R10),对每个子文件进行直接插入排序结果为：
13 27 49' 55 04 49 38 65 97 76
第二趟以步长为 3对第一趟排序结果分割为 3 个子文件：
(R1,R4,R7,R10) (R2,R5,R8) (R3,R6,R9)
对每个子文件进行直接插入排序,结果为：
13 04 49' 38 27 49 55 65 97 76
第三趟以步长为 1对第二趟排序结果进行直接插入排序,结果为：
04 13 27 38 49' 49 55 65 76 97
10.2 插入排序
4．希尔排序的特点
⑴ 子文件（子序列）的构成不是简单地“逐段分割”
，而是将相隔某个“增量”的记录组成一个子文件
。
⑵ 增量序列应是递减，且最后一个必须为 1。
⑶ 希尔排序法是不稳定的。
5,希尔排序算法的实现 p书 272。
10.3 快速排序一,快速排序 （ 目前内部排序中最快的方法 ）
⒈ 基本思想,选取某个记录,（ 通常选文件的第一个记录 ）,将所有关键字不大于它的记录放在它的前面,将所有关键字不小于它的记录放在它的后面,这样遍历一趟文件后,将文件以该记录为界分为两部分
,然后对各部分重复上述过程,直到每一部分仅剩一个记录为止 。
⒉ 具体步骤
(1) 置变量 i,j初值分别为文件的首、尾记录位置；
选取文件首记录 r[i]，并将其关键字赋给变量 x；
(2) 从 j 位置开始向前搜索，
(3) 直到遇到第一个关键字小于 x的记录，
(4) 并将 r[j]移至 r[i]；
(5) 从 i 位置开始向后搜索，
(6) 直到遇到第一个关键字大于 x的记录，
(7) 并将 r[i]移至 r[j]；
(8) 重复 (2)
(9) 直到 i＝＝ j，
(10) 并将 x移至 r[i]，以 r[i]为中枢将文件分为 r[1..i-1]和
r[i+1..n]两部分，完成一趟排序；
(11) 重复 (1)至 (10)，直到每一部分只剩上一个记录，整个文件已有序，快速排序算法结束。
10.3 快速排序
3,示意图：
x 5
向后搜索
r[i],key＞ x
i=j
7
r[i] r[j]
r[j],key≥x
向前搜索
2 j
3
r[j],key＜ x
84
r[j] r[i]
r[i],key≤x 6 9
10
x r[i]
1
x
1 ≤x i-1 i i+1 ≥x n
注意：向前搜索时,j=j-1，且 r[i]空闲；
向后搜索时,i=i-1，且 r[j]空闲。
10.3 快速排序
⒊ 一趟快速排序算法 P书 275。
初始关键字 49 38 65 97 76 13 27 49
i j j
1次交换之后 27 38 65 97 76 13 49
i i j
2次交换之后 27 38 97 76 13 65 49
i j j
3次交换之后 27 38 13 97 76 65 49
i i j
4次交换之后 27 38 13 76 97 65 49
ij j完成一趟排序 27 38 13 49 76 97 65 49
10.3 快速排序初始状态 49 38 65 97 76 13 27 49
一次划分 27 38 13 49 76 97 65 49
分别进行 13 27 38
结束结束 49 65 76 97
49 65 结束结束有序序列 13 27 38 49 49 65 76 97
10.3 快速排序
⒋ 快速排序算法特点
⑴ 快速排序算法是不稳定的 。
对待排序文件 49 49' 38 65，
快速排序结果为,38 49' 49 65
⑵ 快速排序的效率跟初始文件中关键字的排列和选取划分的记录有关 。 当初始文件按关键字有序 (正序或逆序 )时,性能最差,时间复杂度为 O(n2)；
⑶ 常用,三者取中,法来选取划分记录,即取首记录 r[s].key.尾记录 r[t].key和中间记录 r[(s+t)/2].key三者的中间值为划分记录 。
(4)快速排序算法的平均时间复杂度为 O(nlogn)。
10.3 快速排序二、起泡排序（ P书 273）
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第 n-1个记录和第 n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前 n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
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 78
49 97
初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟
10.4 选择排序一,简单选择排序
⒈ 基本思想,对文件进行 n-1趟排序，第 i趟
(i=1,2,...n-1)是在从 i到 n的 n-i+1个记录中选择关键字最小的记录，并将它与第 i个记录进行交换。
1 n
第一趟,n个记录第二趟,n-1
．．．,．．
第ｎ -1趟 2
比较次数
n-1
n-2
1
10.4 选择排序
⒉ 简单选择排序算法
Smp_Selecpass(ListType &r,int i)
{ k=i;
for(j=i+1;j<n;i++)
if (r[j].key<r[k].key) k=j;
if (k!=i)
{ t=r[i];r[i]=r[k];r[k]=t;}
}
Smp_Sort(ListType &r)
{ for(i=1;i<n-1;i++)
Smp_Selecpass(r,i);
}
10.4 选择排序
⒊ 算法分析
⑴ 交换次数：正序时交换次数最少,为 0次,
逆序时最多,为 n-1次 。
⑵ 比较次数：与初始文件关键字排列无关,
为 n(n-1)/2次 。
⑶ 简单选择排序时间复杂度为 O(n2)，
并且是稳定的排序 。
10.4 选择排序二,堆排序
⒈ 堆的定义,n个元素的序列 {K1,K2,...,Kn}
若满足,Ki≤K2i 或 Ki≥K2i
Ki≤K2i +1 Ki≥K2i+1
(i=1,2,..,n/2)
称为堆。
10.4 选择排序若将堆视为一个完全二叉树 （ 图一 ）,则堆的含义为：
完全二叉树中所有非终端结点的值均不大于 (或不小于 )其左,
右孩子的值 （ 图二 ） 。 堆顶元素 (即完全二叉树的根 )是序列中最小 (或最大 )的元素 。
k3
k1
k5
k2
k4
．．．．．．．．
图一
24
12
47
38
85
91
30 53
图二
10.4 选择排序
⒉ 堆排序基本思想
⑴ 以初始关键字序列,建立堆；
⑵ 输出堆顶最小元素；
⑶ 调整余下的元素,使其成为一个新堆；
⑷ 重复 ⑵,⑶ n 次,得到 一个有序序列 。
关键要解决⑴和⑶，即如何由一个无序序列建成一个堆? 如何调整余下的元素成为一个新堆?
10.4 选择排序
⒊ 调整方法
⑴ 将堆顶元素和堆的最后一个元素位置交换；
⑵ 然后以当前堆顶元素和其左,右子树的根结点进行比较 (此时,左,右子树均为堆 ),并与值较小的结点进行交换；
⑶ 重复 ⑵,继续调整被交换过的子树,直到叶结点或没进行交换为止 。
称这个调整过程为 "筛选 "。
10.4 选择排序例：
27
13
76
38
49’
97
65 49
输出 13
27
97
76
38
49’
13
65 49
筛选
49
27
76
38
49’
13
65 97
筛选结果 输出 27
49
97
76
38
49’
13
65 27
1
2
49
38
76
49’
97
13
65 27
10.4 选择排序筛选 筛选结果 输出 38
10.4 选择排序
4 无序序列建堆过程方法：从完全二叉树的最后一个非终端结点
n/2开始,反复调用筛选过程,直到第一个结点,则得到一个堆 。
13
49
76
38
49’
97
65 27
65
49
76
38
97
49’
13 27
27
13
76
38
49’
97
65 49
例,{49,38,65,97,76,13,27,49’}
10.4 选择排序
5.堆排序过程 (见书 P281-282）
堆排序是不稳定的，时间复杂度为 O(nlogn)。
10.5 归并排序
⒈ 归并概念,把 2 个有序子文件合并成一个有序文件的过程,称为 2-路归并 。
归并排序基本思想：⑴将文件的每个记录视为一个有序子文件；⑵然后两两子文件进行 2-路归并；⑶重复⑵，直到只剩一个长度为 n的有序文件例：初始关键字,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
每个记录视为一个有序子文件，两个子文件进行归并，得 4
个有序子文件。
⒉ 归并排序过程
void merge(listtype r,r2; int l,m,n;);
{ //t[s..m]和 r[m+1..n]为两个有序子文件,归并结果存放在 r2[s..n]中
i=s; j=m+1; k=s-1;
WHILE(i≤m)AND(j≤n) DO
{ k=k+1; //k为下一次存入 r2的位置
if r[i].key≤r[j].key ｛ r2[k]=r[i]; i=i+1;｝
else { r2[k]=r[j]; i=j+1;}}
if(i≤m) r2[k+1..n]=r[i..m];
if (j≤n) r2[k+1..n]=r[j..n] ;
{将其中一个文件的余下部分复制到 r2的尾部 }
}//merge
归并排序是稳定的，时间复杂度为 O(nlogn)，
需要和待排序记录相等数量的辅助空间 r2。
10.6 基数排序基数排序法是一种用多关键字排序思想对单逻辑关键字进行排序,而无需进行关键字比较的新排序方法,其基本操作是,分配,和,收集,。
⒈ 基数排序方法,基数排序是按组成关键字的各位的值进行分配和收集,与前面介绍的排序方法不同,
它无需进行关键字之间的比较 。
设关键字有 d 位，每位的取值范围为 r (称为基数 )
，则需要进行 d 趟分配与收集，需要设立 r 个队列。
例如，若每位是十进制数字，则需要设立 10个队列，
若每位由小写字母组成，则要设立 26个队列 。
10.6 基数排序
2,基数排序的步骤
⑴ 从关键字的低位开始进行第 i趟 (i=1,2,...d)分配即将单链表中的记录依次按关键字的第 i位分配到相应编号的队列中；
⑵ 分配完毕后,将各队列的记录按队列编号顺序收集成一个单链表；
⑶ 重复 ⑴⑵,直到第 d趟收集完毕,所得单链表已成为有序表 。
10.6 基数排序例,初始 278— 109— 063— 930— 589— 184— 505— 269— 008— 083
0 1 2 3 4 5 6 7 8 9
第一趟分配 269
083 008 589
930 063 184 505 278 109
第一趟收集 930— 063— 083— 184— 505— 278— 008— 109— 589— 269
第二趟分配 109 589
008 269 184
505 930 063 278 083
第二趟收集 505— 008— 109— 930— 063— 269— 278— 083— 184— 589
第三趟分配 083
063 184 278 589
008 109 269 505 930
第三趟收集 008— 063— 083— 109— 184— 269— 278— 505— 589— 930
10.6 基数排序
⒊ 基数排序的特点
⑴ 基数排序的基本操作是 "分配 "和 "收集 ",而不是关键字之间的比较；
⑵ 基数排序是稳定的,其时间复杂度为 O(d(n+rd))，
其中 n是记录数,d是关键字的位数,r是关键字各位的值域 。
⑶ 基数排序要进行 d趟分配和收集,需 r个队列数据结构的学习重点
1、如何描述一种新的抽象数据类型？
2、如何分析算法的优劣？
3、线性表的主要特征。
4、线性表的存储表示（顺序表示、单向链表、循环链表、
双向链表）
5、特殊的线性表：栈、队列、串、广义表
6、二叉树的定义、性质、存储结构、遍历算法
7、图的定义、术语、存储结构
8、静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
9、插入排序、快速排序、选择排序总复习
基本概念
插入排序
快速排序
选择排序
归并排序
基数排序
10.1 基本概念设含有 n个记录的文件 {R1,R2,...,Rn},其相应的关键字为 {K1,K2,...,Kn},将记录按关键字值非递减 (或非递增 )顺序排列的过程,称为 排序 。
对所有的 Ki=Kj (i≠j),若排序前 Ri领先于 Rj,排序后
Ri仍领先于 Rj,则称该排序方法是 稳定的,反之,称为 不稳定 的 。
稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置 （ 即领先关系 ） 是否变化 。
10.1 基本概念内部排序,待排序文件的全部记录存放在内存进行的排序,称为内部排序 。
外部排序,排序过程中需要进行内外存数据交换的排序,称为外部排序 。
10.1 基本概念内排序分类按排序过程依据的原则分为：插入排序交换排序选择排序归并排序计数排序按排序过程所需的工作量分：简单排序 O(n2)
先进排序 O(nlogn)
基数排序 O(d,n)
10.2 插入排序一,直接插入排序 (最简单的排序方法 ）
⒈ 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置 (有序子文件记录数增 1)
例如：已有待排序文件为,38,65,49,76,97
首先将文件的第一个记录,视为有序文件,然后从第二个记录开始,直到最后一个记录,依次将他们插入到有序文件的合适位置 。
10.2 插入排序
⒉ 直接插入排序算法
void InsertSort(SqList &L)；
{for( i=2;i<= n;i++)
{ r[0]=r[i];
j=i-1; /*r[1]～ r[i-1]为有序子文件 */
while (r[0].key＜ r[j].key)
{ r[j+1]=r[j]; j=j-1 }; /*确定插入位置并移动 */
r[j+1]=r[0];
}
}//strainsort
10.2 插入排序
⒊ 算法分析
⑴ 空间上,只需 i,j两个整型变量和一个记录的辅助空间 r[0],r[0]
作为,监视哨,,控制待插入元素相对于有序子文件为最小时
WHILE循环的结束,同时也用于暂存待插入元素 。
⑵ 时间上,只包含比较关键字和移动记录两种操作 。
① 比较次数,
1/.当待初始文件按关键字递增有序 (正序 )时：
a.对每个记录只进行一次比较,整个排序过程共
n进行了 ∑1=n-1次比较 (最少 )；
i=2
b.每个记录都要进行 r[i]移到 r[0]和 r[0]移到 r[j+1]两次移动,
因此共移动 2(n-1)次 (最少 )。
10.2 插入排序
2/,当待排序文件按关键字非递增有序 (逆序 )时
① 记录 r[i](i=2,3,...n)均要和前 i-1个记录及 r[0]进行比较,整个排序过程共进行了
n∑ i=(n+2)(n-1)/2次比较 (最多 )；
i=2
② 移动记录次数：每个记录都要进行 r[i]移动到 r[0]和 r[0]移动到 r[j+1]两次移动,另外当 r[i].key＜ r[j].key时,还将 r[j]移动到 r[j+1],所以,当初始文件为正序时,移动记录次数最少为 2（ n-1） 次,当初始文件为逆序时移动记录次数最多为
n
∑ (i-1)+2(n-1)=(n+4)(n-1)/2次 (最多 )。
i=2
10.2 插入排序
⑶ 结论
1/,直接插入排序的效率与待排文件的关键字排列有关；
2/,直接插入排序的时间复杂度为 O(n2)；
3/,直接插入排序是稳定的 (这一点由过程中 WHILE语句的条件,＜,保证的 )。 void InsertSort(SqList &L)；
{for( i=2;i<= n;i++)
{ r[0]=r[i];
j=i-1;
while (r[0].key＜ r[j].key)
{ r[j+1]=r[j]; j=j-1; };
r[j+1]=r[0];}
}//strainsort
10.2 插入排序二,折半插入排序由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，
从而可减少比较次数。
10.2 插入排序
Void BInsertSort( SqList &L)；
{ for ( i=2;i<=L.length;i++)
{low=1； high=i-1 ； L.r[0]=L.r[i]；
while (low≤high)
{m=(low+high)/2；
if (L.r[i],key＜ L.r[m],key) //＜确保稳定，若改为 ≤，则不稳定
high＝ｍ -1;
else low=m+1； }
for ( k=i-1;k>= high+1;k--) L.r[k+1]=L.r[k]；
L.r[high+1]=L.r[0];}
}//BInsertSort
移动次数未变，故仍为 O(n2)
10.2 插入排序三,希尔排序 （ Shell`s Methool） (又称为缩小增量排序 )
⒈ 基本思想,分割成若干个较小的子文件,对各个子文件分别进行直接插入排序,当文件达到基本有序时,再对整个文件进行一次直接插入排序 。
⒉ 依据,⑴ 若待排序文件 "基本有序 ",即文件中具有特性：
r[i].key＜ Max {r[j ]} 1≤j＜ i的记录数较少,
则文件中大多数记录都不需要进行插入 。
⑵ 基本有序时,直接插入排序效率可以提高,接近于 O(n)。
10.2 插入排序
⒊ 例,设初始关键字为,49 38 65 97 76 13 27 49' 55 04
第一趟以步长为 5分割为 5个子文件,(R1,R6) (R2,R7) (R3,R8)
(R4,R6) (R5,R10),对每个子文件进行直接插入排序结果为：
13 27 49' 55 04 49 38 65 97 76
第二趟以步长为 3对第一趟排序结果分割为 3 个子文件：
(R1,R4,R7,R10) (R2,R5,R8) (R3,R6,R9)
对每个子文件进行直接插入排序,结果为：
13 04 49' 38 27 49 55 65 97 76
第三趟以步长为 1对第二趟排序结果进行直接插入排序,结果为：
04 13 27 38 49' 49 55 65 76 97
10.2 插入排序
4．希尔排序的特点
⑴ 子文件（子序列）的构成不是简单地“逐段分割”
，而是将相隔某个“增量”的记录组成一个子文件
。
⑵ 增量序列应是递减，且最后一个必须为 1。
⑶ 希尔排序法是不稳定的。
5,希尔排序算法的实现 p书 272。
10.3 快速排序一,快速排序 （ 目前内部排序中最快的方法 ）
⒈ 基本思想,选取某个记录,（ 通常选文件的第一个记录 ）,将所有关键字不大于它的记录放在它的前面,将所有关键字不小于它的记录放在它的后面,这样遍历一趟文件后,将文件以该记录为界分为两部分
,然后对各部分重复上述过程,直到每一部分仅剩一个记录为止 。
⒉ 具体步骤
(1) 置变量 i,j初值分别为文件的首、尾记录位置；
选取文件首记录 r[i]，并将其关键字赋给变量 x；
(2) 从 j 位置开始向前搜索，
(3) 直到遇到第一个关键字小于 x的记录，
(4) 并将 r[j]移至 r[i]；
(5) 从 i 位置开始向后搜索，
(6) 直到遇到第一个关键字大于 x的记录，
(7) 并将 r[i]移至 r[j]；
(8) 重复 (2)
(9) 直到 i＝＝ j，
(10) 并将 x移至 r[i]，以 r[i]为中枢将文件分为 r[1..i-1]和
r[i+1..n]两部分，完成一趟排序；
(11) 重复 (1)至 (10)，直到每一部分只剩上一个记录，整个文件已有序，快速排序算法结束。
10.3 快速排序
3,示意图：
x 5
向后搜索
r[i],key＞ x
i=j
7
r[i] r[j]
r[j],key≥x
向前搜索
2 j
3
r[j],key＜ x
84
r[j] r[i]
r[i],key≤x 6 9
10
x r[i]
1
x
1 ≤x i-1 i i+1 ≥x n
注意：向前搜索时,j=j-1，且 r[i]空闲；
向后搜索时,i=i-1，且 r[j]空闲。
10.3 快速排序
⒊ 一趟快速排序算法 P书 275。
初始关键字 49 38 65 97 76 13 27 49
i j j
1次交换之后 27 38 65 97 76 13 49
i i j
2次交换之后 27 38 97 76 13 65 49
i j j
3次交换之后 27 38 13 97 76 65 49
i i j
4次交换之后 27 38 13 76 97 65 49
ij j完成一趟排序 27 38 13 49 76 97 65 49
10.3 快速排序初始状态 49 38 65 97 76 13 27 49
一次划分 27 38 13 49 76 97 65 49
分别进行 13 27 38
结束结束 49 65 76 97
49 65 结束结束有序序列 13 27 38 49 49 65 76 97
10.3 快速排序
⒋ 快速排序算法特点
⑴ 快速排序算法是不稳定的 。
对待排序文件 49 49' 38 65，
快速排序结果为,38 49' 49 65
⑵ 快速排序的效率跟初始文件中关键字的排列和选取划分的记录有关 。 当初始文件按关键字有序 (正序或逆序 )时,性能最差,时间复杂度为 O(n2)；
⑶ 常用,三者取中,法来选取划分记录,即取首记录 r[s].key.尾记录 r[t].key和中间记录 r[(s+t)/2].key三者的中间值为划分记录 。
(4)快速排序算法的平均时间复杂度为 O(nlogn)。
10.3 快速排序二、起泡排序（ P书 273）
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第 n-1个记录和第 n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前 n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
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 78
49 97
初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟
10.4 选择排序一,简单选择排序
⒈ 基本思想,对文件进行 n-1趟排序，第 i趟
(i=1,2,...n-1)是在从 i到 n的 n-i+1个记录中选择关键字最小的记录，并将它与第 i个记录进行交换。
1 n
第一趟,n个记录第二趟,n-1
．．．,．．
第ｎ -1趟 2
比较次数
n-1
n-2
1
10.4 选择排序
⒉ 简单选择排序算法
Smp_Selecpass(ListType &r,int i)
{ k=i;
for(j=i+1;j<n;i++)
if (r[j].key<r[k].key) k=j;
if (k!=i)
{ t=r[i];r[i]=r[k];r[k]=t;}
}
Smp_Sort(ListType &r)
{ for(i=1;i<n-1;i++)
Smp_Selecpass(r,i);
}
10.4 选择排序
⒊ 算法分析
⑴ 交换次数：正序时交换次数最少,为 0次,
逆序时最多,为 n-1次 。
⑵ 比较次数：与初始文件关键字排列无关,
为 n(n-1)/2次 。
⑶ 简单选择排序时间复杂度为 O(n2)，
并且是稳定的排序 。
10.4 选择排序二,堆排序
⒈ 堆的定义,n个元素的序列 {K1,K2,...,Kn}
若满足,Ki≤K2i 或 Ki≥K2i
Ki≤K2i +1 Ki≥K2i+1
(i=1,2,..,n/2)
称为堆。
10.4 选择排序若将堆视为一个完全二叉树 （ 图一 ）,则堆的含义为：
完全二叉树中所有非终端结点的值均不大于 (或不小于 )其左,
右孩子的值 （ 图二 ） 。 堆顶元素 (即完全二叉树的根 )是序列中最小 (或最大 )的元素 。
k3
k1
k5
k2
k4
．．．．．．．．
图一
24
12
47
38
85
91
30 53
图二
10.4 选择排序
⒉ 堆排序基本思想
⑴ 以初始关键字序列,建立堆；
⑵ 输出堆顶最小元素；
⑶ 调整余下的元素,使其成为一个新堆；
⑷ 重复 ⑵,⑶ n 次,得到 一个有序序列 。
关键要解决⑴和⑶，即如何由一个无序序列建成一个堆? 如何调整余下的元素成为一个新堆?
10.4 选择排序
⒊ 调整方法
⑴ 将堆顶元素和堆的最后一个元素位置交换；
⑵ 然后以当前堆顶元素和其左,右子树的根结点进行比较 (此时,左,右子树均为堆 ),并与值较小的结点进行交换；
⑶ 重复 ⑵,继续调整被交换过的子树,直到叶结点或没进行交换为止 。
称这个调整过程为 "筛选 "。
10.4 选择排序例：
27
13
76
38
49’
97
65 49
输出 13
27
97
76
38
49’
13
65 49
筛选
49
27
76
38
49’
13
65 97
筛选结果 输出 27
49
97
76
38
49’
13
65 27
1
2
49
38
76
49’
97
13
65 27
10.4 选择排序筛选 筛选结果 输出 38
10.4 选择排序
4 无序序列建堆过程方法：从完全二叉树的最后一个非终端结点
n/2开始,反复调用筛选过程,直到第一个结点,则得到一个堆 。
13
49
76
38
49’
97
65 27
65
49
76
38
97
49’
13 27
27
13
76
38
49’
97
65 49
例,{49,38,65,97,76,13,27,49’}
10.4 选择排序
5.堆排序过程 (见书 P281-282）
堆排序是不稳定的，时间复杂度为 O(nlogn)。
10.5 归并排序
⒈ 归并概念,把 2 个有序子文件合并成一个有序文件的过程,称为 2-路归并 。
归并排序基本思想：⑴将文件的每个记录视为一个有序子文件；⑵然后两两子文件进行 2-路归并；⑶重复⑵，直到只剩一个长度为 n的有序文件例：初始关键字,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
每个记录视为一个有序子文件，两个子文件进行归并，得 4
个有序子文件。
⒉ 归并排序过程
void merge(listtype r,r2; int l,m,n;);
{ //t[s..m]和 r[m+1..n]为两个有序子文件,归并结果存放在 r2[s..n]中
i=s; j=m+1; k=s-1;
WHILE(i≤m)AND(j≤n) DO
{ k=k+1; //k为下一次存入 r2的位置
if r[i].key≤r[j].key ｛ r2[k]=r[i]; i=i+1;｝
else { r2[k]=r[j]; i=j+1;}}
if(i≤m) r2[k+1..n]=r[i..m];
if (j≤n) r2[k+1..n]=r[j..n] ;
{将其中一个文件的余下部分复制到 r2的尾部 }
}//merge
归并排序是稳定的，时间复杂度为 O(nlogn)，
需要和待排序记录相等数量的辅助空间 r2。
10.6 基数排序基数排序法是一种用多关键字排序思想对单逻辑关键字进行排序,而无需进行关键字比较的新排序方法,其基本操作是,分配,和,收集,。
⒈ 基数排序方法,基数排序是按组成关键字的各位的值进行分配和收集,与前面介绍的排序方法不同,
它无需进行关键字之间的比较 。
设关键字有 d 位，每位的取值范围为 r (称为基数 )
，则需要进行 d 趟分配与收集，需要设立 r 个队列。
例如，若每位是十进制数字，则需要设立 10个队列，
若每位由小写字母组成，则要设立 26个队列 。
10.6 基数排序
2,基数排序的步骤
⑴ 从关键字的低位开始进行第 i趟 (i=1,2,...d)分配即将单链表中的记录依次按关键字的第 i位分配到相应编号的队列中；
⑵ 分配完毕后,将各队列的记录按队列编号顺序收集成一个单链表；
⑶ 重复 ⑴⑵,直到第 d趟收集完毕,所得单链表已成为有序表 。
10.6 基数排序例,初始 278— 109— 063— 930— 589— 184— 505— 269— 008— 083
0 1 2 3 4 5 6 7 8 9
第一趟分配 269
083 008 589
930 063 184 505 278 109
第一趟收集 930— 063— 083— 184— 505— 278— 008— 109— 589— 269
第二趟分配 109 589
008 269 184
505 930 063 278 083
第二趟收集 505— 008— 109— 930— 063— 269— 278— 083— 184— 589
第三趟分配 083
063 184 278 589
008 109 269 505 930
第三趟收集 008— 063— 083— 109— 184— 269— 278— 505— 589— 930
10.6 基数排序
⒊ 基数排序的特点
⑴ 基数排序的基本操作是 "分配 "和 "收集 ",而不是关键字之间的比较；
⑵ 基数排序是稳定的,其时间复杂度为 O(d(n+rd))，
其中 n是记录数,d是关键字的位数,r是关键字各位的值域 。
⑶ 基数排序要进行 d趟分配和收集,需 r个队列数据结构的学习重点
1、如何描述一种新的抽象数据类型？
2、如何分析算法的优劣？
3、线性表的主要特征。
4、线性表的存储表示（顺序表示、单向链表、循环链表、
双向链表）
5、特殊的线性表：栈、队列、串、广义表
6、二叉树的定义、性质、存储结构、遍历算法
7、图的定义、术语、存储结构
8、静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
9、插入排序、快速排序、选择排序总复习
