,数据结构,
第十章 内部排序第十章 内部排序第 2页第十章 内部排序内容和要求排序及有关的概念，直接插入排序、二分法插入排序、表插入排序,shell排序，直接选择排序、树形选择排序、堆排序、冒泡排序和快速排序、基数排序、归并排序。
要求通过学习，掌握排序的各种方法，为解决实际问题奠定理论基础的技术基础。了解排序和排序码的概念，
熟悉 直接插入排序、二分法插入排序、表插入排序
,Shell排序的方法和时空复杂性；
掌握 堆排序、快速排序、基数排序、归并排序的基本思路，排序方法，算法的主要步骤和时空复杂性；
知道 shell 排序和树形选择排序方法 。
第十章 内部排序第 3页概 述如何对一大批按关键字无序的数据元素或记录，高效率地将它们重新排列成一个按关键字有序的序列，是计算机应用中的重要课题之一。
可以假定被排序的对象是由一组记录组成的文件，而记录则由若干个数据项
（或字段、域）组成，其中有一项可用来标识一个记录，称为 关键字,它具关键字值。关键字是排序操作的依据。
第十章 内部排序第 4页定义 1,假设含 n 个记录的序列为
{R1,R2,···,Rn} (10-1)
其相应的关键字序列为
{K1,K2,···,Kn}
需确定 1,2,··,n 的一种排列 P1,P2,···,Pn,使其相应的关键字满足如下的非递减（或非递增）关系
Kp1≤Kp2 ≤··· ≤ Kpn (10-2)
即使式 (10-1) 的序列成为一个按关键字有序的序列
{Rp1,Rp2,···,Rpn } (10-3)
这样一种操作称为排序。
概 述?
显然，当待排记录的关键字均不相同时，则排序的结果是唯一的，否则排序的结果不一定唯一。特别地,按主关键字进行排序，其排序的结果是唯一的 。而若按次关键字进行排序，结果不一定唯一。
第十章 内部排序第 5页定义 2,如果待排序的文件中，存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是 稳定的 ；
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。
定义 3,在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换,则称为内部排序，简称内排序； 反之，若排序过程中要进行数据的内、外存交换,则称之为外部排序，简称外排序 。
概 述?
第十章 内部排序第 6页概 述?
各种排序方法可以按照不同的原则加以分类。
内部排序方法的分类：
一、按所用策略进行分类
(1) 插入排序
(2) 交换排序
(3) 选择排序
(4) 归并排序
(5) 计数排序二、按所需工作量进行分类
(1) 简单的排序方法 O(n2)
(2) 先进的排序方法 O(nlogn)
(3) 基数排序 O(d?n)
第十章 内部排序第 7页在排序的过程中需进行的 两种基本操作,
(1) 比较两个关键字的大小 ；
(2) 将记录从一个位置移动至另一个位置。
前一个操作对大多数排序方法来说都是必要的，而后一种操作可以通过改变记录的存储方式来予以避免。
概 述?
排序的时间开销是算法好坏的最重要的标志。 排序的时间开销主要可以用算法执行中 关键字的比较次数 和记录的移动次数 来衡量。
第十章 内部排序第 8页概 述?
设待排记录的数据类型为
#define MAX_SIZE 20
typedef int KeyType
typedef struct {
KeyType key;
InfoType otherInfo;
} RecType;
typedef struct {
RecType r[MAX_SIZE + 1];
int Length;
}SqList;
三种存储方式：
（ 1）待排序记录存放在地址连续的存储单元上。
（ 2）待排序记录存以静态链表存储，记录间的次序由指针指示。
（ 3）待排序记录存放在在连续存储单元中，另设指向各个记录地址的指针向量。
第十章 内部排序第 9页插 入 排 序插入排序的基本思想是,每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的表或文件中的适当位置，直到全部插入完为止。
直接插入排序基本操作是 将一个记录插入到已排好序的有序表中，
从而得到一个新的、记录数增 1的有序表。
直接插入排序 分趟 进行,一般情况下，第 i 趟直接插入排序的操作为,在含在 i-1 个记录的有序子序列
r[1..i-1] 中，首先查找 r[i]的插入位置 j,使得
r[j].key? r[i].key< r[j+1].key (0? j<i)
在 r[j]之后 插入一个记录 r[i],得到含有 i 个记录的有序子序列 r[1..i] 。
第十章 内部排序第 10页示例 1 设待排关键字集合为
{49,38,65,97,76,13,27,49}
[初始关键字 ] (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)
↑监视哨 图 10.1 直接插入排序示例直接插入排序第十章 内部排序第 11页直接插入排序算法描述（ n 个记录，共进行 n-1 趟插入）
straisort( SqList &l )
//对 r[1..n] 进行直接插入排序，执行本算法后,r[1..n]
中的记录按关键字非递减有序排列
{ for( i = 2; i <= l.Length; i++ )
if( l.r[i].key < l.r[i-1].key )
{ 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];
}
}
直接插入排序第十章 内部排序第 12页
(1) 若初始序列按关键字递增有序（简称正序），则最小比较次数最小移动次数 0
直接插入排序算法分析直接插入排序算法由两重循环组成，外循环表示要进行 n-1
趟插入排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。
直接插入排序是稳定的排序方法 。
(2) 若初始文件按关键字递减有序（简称逆序或反序），则最大比较次数最小移动次数
(3) 若初始文件按关键字随机排列，则关键字的比较次数和移动次数均为 (n2)/4
故直接插入排序算法的时间复杂度为 O(n2)。空间复杂度为 O(1).
第十章 内部排序第 13页在直接插入排序的一趟 (第 i 趟 ) 算法中，搜索操作可由在区间
[1,i-1] 上进行折半查找来实现 。如此进行的插入排序称为折半插入排序 (Binary Insertion Sort)。
折半插入排序
BInsertSort( SqList &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( l.r[0].key < l.r[m].key ) hight = m – 1;
else low = m + 1;
} //while
for( j = i – 1; j >= high + 1; j++ ) r[j+1] = r[j]; //记录后移
l.r[high+1] = r[0]; //插入 r[i]
} //算法 10.4
折半插入排序的时间复杂度仍为 O(n2)。减少了比较次数，其排序方法是稳定的。
第十章 内部排序第 14页
2-路插入排序在折半插入排序基础上的一种改进算法,其目的是减少排序过程中移动记录的次数，但为此需要 n 个记录的辅助空间。
算法思想,另设一个和 L 同类型的数组 d，将它看成是一个循环向量，并设两个指针 first 和 final 分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。首先将 r[1] 赋值给 d[1]，并将 d[1] 看成是在排好序的序列中处于中间位置的记录，然后从 r
中第 2个记录起依次插入到 d[1] 之前或之后的有序序列中。
第十章 内部排序第 15页示例 2 设待排序关键字集合同示例 1，采用 2-路插入排序算法
[初始关键字 ] 49 38 65 97 76 13 27 49
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
图 10.2 2-路插入排序示例第十章 内部排序第 16页在 2-路插入排序中，记录移动的次数会减少
，但是不能绝对避免移动记录。
在通常情况下，移动记录的次数约为 n2/8。
极端情况下，当 r[1] 是待排序记录中关键字最小或最大的记录时,2-路插入排序就完全失去它的优越性。
如希望不移动记录，只有改变存储结构，采用表插入排序。
2-路插入排序第十章 内部排序第 17页表插入排序算法思想,以静态链表作为存储结构（ 用数组描述的链表，有整数指示域）。 在插入 Ri 时,R1到 Ri-1
已用指针按关键字不减次序链接起来，这时采用顺序比较方法找到 Ri 应该插入的位置，然后作链表的插入，使得到从 R1—Ri 的已排序的链表。如此反复，
直到把 Rn 插入链表，排序过程结束。
为使插入方便，在数组中多设一个下标为 0 的分量作为表头结点，并令表头记录的关键字为最大整数
maxint。排序开始时，先令表头结点和第一个记录结点组成一个循环链表，然后从 i=2 起，依次将第 i 个结点插入链表。
表插入排序解决了在排序过程中不移动记录，但比较次数不变。故其算法的时间复杂度仍是 O(n2).
第十章 内部排序第 18页用于表插入排序的静态链表数据结构
#define SIZE 100
typedef struct{
RecType rc; //关键字,Info
int next
} SLNode;
typedef struct{
SLNode r[SIZE];
int length;
}SLinkListType;
示例 3 设待排序关键字集合同示例 1，采用表插入排序算法表插入排序第十章 内部排序第 19页
1 2 3 4 5 6 7 80
49 38 65 97 76 13 27 49maxint
0 - - - - - - -1初始
49 38 65 97 76 13 27 49maxint
0 1 - - - - - -2i=2
49 38 65 97 76 13 27 49maxint
3 1 0 - - - - -2i=3
49 38 65 97 76 13 27 49maxint
3 1 4 0 - - - -2i=4
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 - - -2i=5
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 2 - -6i=6
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 7 2 -6i=7
49 38 65 97 76 13 27 49maxint
8 1 5 0 4 7 2 36i=8
第十章 内部排序第 20页表插入排序的结果只是求得一个有序链表，为了能应用有序表的折半查找，尚需对记录进行重新排列。
表插入排序重排记录的做法是,顺序扫描有序链表，将链表中第
i 个结点移动至第 i 个分量中。
若
SLinkListType rsl;
则一般情况下,若第 i 个最小关键字的结点是数组中下标为 p 且 p>i 的分量，则互换 rs1[i] 和 rs1[p]，且令
rs1[i] 中指针域的值改为 p； 由于此时数组中所有小于 i 的分量中已是“到位”的记录，则当 p<i 时，应顺链继续查找直到 p≥i 为止。
第十章 内部排序第 21页
1 2 3 4 5 6 7 80
49 38 65 97 76 13 27 49maxint
8 1 5 0 4 7 2 36初始
13 38 65 97 76 49 27 49maxint
(6) 1 5 0 4 8 2 37
i=1
P=6
13 27 65 97 76 49 38 49maxint
(6) (7) 5 0 4 8 1 32
i=2
P=7
13 27 38 97 76 49 65 49maxint
(6) (7) (7) 0 4 8 5 31
i=3
P=(2)=7
13 27 38 49 76 97 65 49maxint
(6) (7) (7) (6) 4 0 5 38
i=4
P=(1)
6
13 27 38 49 49 97 65 76maxint
(6) (7) (7) (6) (8) 0 5 43
i=5
P=8
13 27 38 49 49 65 97 76maxint
(6) (7) (7) (6) (8) (7) 0 45
i=6
P=(3)
7
13 27 38 49 49 65 76 97maxint
(6) (7) (7) (6) (8) (7) (8) 04
i=7
P=(5)
8
第十章 内部排序第 22页表插入排序
void Arrange( SqLinkType &sl )
{ p = sl.r[0].next;
for( i = 1; i < sl.length; i++ )
{ while( p < i ) p = sl.r[p].next;
q = sl.r[p].next;
if( p != i )
{ sl.r[p] <－ > sl.r[i];
sl.r[i].next = p;
}
p = q;
}
}
算法如下：
在重排过程中，最坏情况是每个记录到位都进行一次交换，因此，重排最多允许有 2(n-1)次记录移动，不增加排序时间复杂度。
第十章 内部排序第 23页希尔排序希尔排序 (Shell`s Method) 又称缩小增量排序
(Diminishing Increment Sort) 。是由 D.L.Shell 在 1959年提出来的。 效率有较大改进。
它的基本作法是,先取定一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组，所有距离为 d1 倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量 d2<d1 重复上述分组和排序，直至所取的增量 dt=1(dt<dt-1<··<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
希尔排序的基本思想是,先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
第十章 内部排序第 24页示例 5 设初始关键字序列集合为 {49,38,65,97
,76,13,27,49,55,04}，则按增量（即步长）
分别取 5,3,1进行希尔排序，三趟排序结果如下所示初始关键字 49 38 65 97 76 13 27 49 55 04
5步分类 13 27 49 55 04 49 38 65 97 76
3步分类 13 04 49 38 27 49 55 65 97 76
1步分类 04 13 27 38 49 49 55 65 76 97
希尔排序的一个特点是,子序列的构成不是简单地
“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。 关键字较小的记录不是一步一步地往前挪动
，而是跳跃式地往前移，从而使得在进行最后一趟增量为 1的插入排序时,序列已基本有序,只要作记录的少量比较和移动即可完成排序 。
第十章 内部排序第 25页希尔排序的算法描述
void shellsort ( SqList &L,int dlta[],int t )
{//本算法对 l.r[1..n] 中记录进行 t 趟希尔排序。 d[1]<n,d[2],··,d[t]=1
为各趟排序的增量序列
for( k =1; k <= t; k++ )
ShellInsert( L,dlta[k] );
} //shellsort 算法 10.5
其中 ShellInsert 为一趟（第 k 趟）希尔排序的算法。
void ShellInsert( SqList &L,int dk )
{ //本算法进行一趟希尔排序,dk 为增量
for( i = dk + 1; i <= L.length; i++ )
if( 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]; //插入
}
} //shellposs 算法 10.4
第十章 内部排序第 26页说明
(1) 在希尔排序算法中，如何选择增量序列才能产生最好的排序效果，是一个困难的数学问题，至今没有得到解决。增量序列可以有各种取法。
Knuth 给出：当 n 在某个特定范围内，希尔排序所需的比较和移动次数约为 n1.3，当 n→∞ 时，可减少到
n(log2n)2.
(2) 希尔排序的时间性能优于直接插入排序。在希尔排序开始时增量较大，分组较多，每组的记录数目少
，故各组内直接插入较快，后来增量 di 逐渐缩小，
分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按 di-1 作为距离排过序，使文件较接近于有序状态。因此，希尔排序在效率上较直接插入排序有较大的改进。
希尔排序第十章 内部排序第 27页插入排序总结
直接插入排序
折半插入排序
– 减少了比较次数 –采用折半查找
2路插入排序
– 减少了记录移动的次数。
表插入排序
– 记录不移动，利用静态链表完成排序。如需要按次序排序，则需要 2(n-1)次移动。
Shell排序
–,跳跃式”的插入排序。目的尽量使排序记录“
基本有序”从而减少比较和移动的次数。
第十章 内部排序第 28页交 换 排 序一类藉助,交换” 进行排序的方法。交换排序的基本思想是,两两比较待排记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录时为止。
两类常用的交换排序,起泡排序和快速排序 。
起泡排序的算法思想很简单,两两比较，随时交换。它亦是分一趟一趟地进行的。若设想把待排序记录数组 R[1..n] 垂直竖立，则按自上而下或从下往上扫描，可视作“石块下沉”或“气泡上浮”的操作过程。
直接交换排序 ——起泡排序第十章 内部排序第 29页示例 1 设初始关键字序列为 {49,38,65,97,76,13，
27,49} 如下所示是自上而下扫描的起泡排序示例
49 38 38 38 38 13 13 13
38 49 49 49 13 27 27 27
65 65 65 13 27 38 38 38
97 76 13 27 49 49 49 49
76 13 27 49 49 49 49 49
13 27 49 65 65 65 65 65
27 49 76 76 76 76 76 76
49 97 97 97 97 97 97 97
初 第 第 第 第 第 第 第始 一 二 三 四 五 六 七关 趟 趟 趟 趟 趟 趟 趟键 排 排 排 排 排 排 排字 序 序 序 序 序 序 序后 后 后 后 后 后 后图 10.6 自上而下扫描的起泡排序示例直接交换排序 ——起泡排序第十章 内部排序第 30页注,判别起泡排序结束的条件：在一趟排序过程中没有进行过交换记录的操作。
起泡排序的算法描述
void bubblesort ( SqList &L )
{ for( i = 1; i <= n-1; i++ ) //最多做 n-1 趟排序
{ noswap = ture; //置未交换的标志
for( j = n-1; j <= i; j-- ) //从底部往上扫描
if( L.r[j+1].key < L.r[j].key ) //交换记录
{ r[j+1]? r[j]; noswap = false };
if( noswap )
return //本趟排序中未发生交换终止算法
}
} //bubblesort
直接交换排序 ——起泡排序第十章 内部排序第 31页起泡排序的算法分析：
(1) 若数组的初始状态是正序的，则一趟扫描就可完成排序，
关键字的比较次数为 n-1，且没有记录移动。也就是说，起泡排序在最好地情况下，时间复杂度是 O(n).
直接交换排序 ——起泡排序
(2) 若初始数组是反序的，则需要进行 n-1 趟排序，每趟排序要进行 n-i 次关键字的比较 (1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。
第十章 内部排序第 32页快速排序快速排序也称分区交换排序，是对起泡排序的一种改进。
基本思想,通过一趟排序将待排记录分割成独立的两部分，
其中一部分记录的关键字均比另一部分关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序。
首先任取一个记录（通常可选第一个记录） 作为标准
（枢轴、支点,pivot）。
然后排列其余记录，将所有关键字 较它小 的记录都安置在它的位置 之前,所有关键字 不小于它 的记录安置在它之后 。
第十章 内部排序第 33页快速排序怎样进行一次划分？
具体方法：
1,附设两个指针 low和 high，分别指向序列的左右两端，设标准关键字为左端第一个，用附加记录 rpivot保存 ;
2,high就地开始，向左搜索，找到第一个关键字小于 x的记录；
low,high始终应保持,low<=high,即 low,high从两端往中间搜索
3,把 high所指记录赋给 i所指位置 ;
4,low就地开始，向右搜索，找到第一个关键字大于 x的记录；
low,high始终应保持,low<=high,即 low,high从两端往中间搜索
5,把 i所指记录赋给 j所指位置 ;
6,重复 2到 5，直到 low=high，把附加记录 rp（支点值）赋给 i位置。
第十章 内部排序第 34页快速排序一趟快速排序示例,设初始关键字为 (49,38,65,97,76,13,27,49)
初始关键字,49 38 65 97 76 13 27 49
支点 l.r[1ow].key =49 ↑low ↑high
high往左搜索,49 38 65 97 76 13 27 49
↑low ↑high↑high
r[low] = r[high],27 38 65 97 76 13 27 49
↑low ↑high
low 往右搜索,27 38 65 97 76 13 27 49
↑low ↑high↑low
r[high] = r[low],27 38 65 97 76 13 65 49
↑low ↑high
6,重复 2到 5，直到 low=high，把附加记录（支点值）赋给 low位置。
完成一趟排序,27 38 13 49 76 97 65 49
low↑high
第十章 内部排序第 35页算法如下：
int Partition( SqList &L,int Low,int High )
{
L.r[0] = L.r[low]; pivotkey = L.r[low].key;
while( Low < High )
{ while( Low < High && L.r[j].key ≥ pivotkey ) j--;
L.r[low] = L.r[High];
while( Low < High && L.r[i].key ≤ pivotkey ) i++;
L.r[High] = L.r[Low];
}
L.r[i] = L.r[0];
return Low;
}
快速排序?
这样排序能否稳定？ 不稳定原则上象这种跳跃式交换的排序方法都不稳定第十章 内部排序第 36页整个快速排序过程可递归进行 （ 在一趟快速排序基础上 ）,快速排序算法：
qsort( SqList &L,int Low,int High )
{ if( Low < High )
{ pivotLoc = Partition( L,Low,High );
qsort( L,Low,pivotLoc - 1);
qsort( L,pivotLoc + 1,High );
}
} //qsort
快速排序?
Void QuickSort( SqList &L )
{ Qsort( L,1,L.length );
}
第十章 内部排序第 37页分别进行块排序,{13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束结束排序结果,13 27 38 49 49 65 76 97
示例：接一趟快速排序结果：
初始,49 38 65 97 76 13 27 49
一次划分之后,{27 38 13} 49 {76 97 65 49}
快速排序?
？这种排序比起泡排序有什么改进，有什么代价一趟排序后，都只把一个记录安排到正确的位置,但快速排序这个位置还起了分隔作用，为下次排序节省了时间。这个位置越居中效果越好。最坏情况是这个位置居于一端，与起泡排序无异。
代价：每趟排序需要一个附加的记录空间。
整个排序因使用递归，还需要栈空间。
第十章 内部排序第 38页算法分析,假定有 n个记录待排快速排序?
(1) 最好的情况,如果第一次选定的就把 n个记录分成 大小相同的两个子块,第一趟排序已有一个记录安排在正确的位置，其比较次数为 n，故所需时间为 O(n)或 Cn（ C为常数）
设对 n 个记录排序时间为 T ( n ),则有：
2
2)( nTCnnT
)l o g()1(l o g
4
42
4
2
2
2
2
2)(
22
nnOnTcnn
n
Tcn
n
T
cn
cn
n
TcnnT
(2) 最坏情况,当初始序列按关键有序或基本有序时，快速排序将蜕化为超泡排序，其时间复杂性为 ).( 2nO
第十章 内部排序第 39页算法分析,假定有 n个记录待排快速排序?
(3) 一般情况：设 为平均时间,则)(nT a v g
1
0
1
)(
2
)()1(
1
)(
n
i
n
k
iTa v g
n
cn
knTa v gkTa v g
n
cnnTa v g
假定 bT a v g?)0( 和 bT a v g?)1( （ b 为某个常量），
则可证明当 )(2 cbk 和 2?n 时，
有,nnknT a v g ln)(
第十章 内部排序第 40页说明：
快速排序?
(1) 快速排序需要一个递归实现（前面各种排序方法只须一个空间）最好情况下（每一趟划分都将序列均匀分割成长度应相近的两个子序列）栈的最大深度为 Log2n+1,但最差时栈的深度为 n。
(2) 为避免蜕化为超泡排序，可改进支点记录（枢轴）的选取，
通常依“三者取中”法则来选取，即比较取三者中关键字取中值点记录为支点关键字。
,.2,].[ k e ytsrk e ysr keytr ].[
(3) 就平均性质而言，快速排序是目前被认为最快的一种内部排序方法。（同数量级排序方法相比，其常数因子 k最小）
(4) 快速排序是不稳定的排序第十章 内部排序第 41页简单选择排序选择排序?
一趟简单选择排序的操作为：
通过 n－ i次关键字间的比较，从 n－ i+1个记录中选出关键字最小的记录，并和第 i个记录交换。 重复上述过程 n－ 1次，即可完成排序。
算法如下：
void smp_selectsort( SqList &L )
{ for( i =1; i <= L.length - 1; i++ )
{ k = i;
for( j = i+1; j <= L.Length; j++ )
if( L.r[j].key < L.r[k].key ) k = j;
if( k≠i ) L.r[i]? L.r[k];
}
} //smp_selectsort
算法分析：
记录移动次数为 0~3(n－ 1),关键字的比较次数为,)1(21 nn
时间复杂性为 ).( 2nO
第十章 内部排序第 42页简单选择排序选择排序?
简单选择排序是不稳定的示例,49 38 65 97 76 27 49 13
No1,13 38 65 97 76 27 49 49
No2,13 27 65 97 76 38 49 49
No3,13 27 38 97 76 65 49 49
No4,13 27 38 49 76 65 97 49
No5,13 27 38 49 49 65 97 76
No6,13 27 38 49 49 65 97 76
No7,13 27 38 49 49 65 76 97
第十章 内部排序第 43页树形选择排序 （ 又称锦标赛排序 ）
选择排序?
简单选择排序时,为了从 n个关键字中找出最少者,需 n－ 1次比较,然后又在 n－ 1个关键字中找次最小的关键字需 n－ 2次比较 。 事实上,后面这 n－ 2次比较中允许比较可能在第一趟的 n－ 1次比较中做过,但是由于第一次比较时,这些结果没有保留下来,所以在第二趟又重复进行 。 树形选择排序可以克服这一缺点 。
具体做法,
把 n 个关键字两两进行比较，取出
2
n
个较小的关键字作为第一步比较的结果保存下来，再把这
2
n
个关键字两两比较，如此反复，一直到比较出最小的关键字为止。
这一过程可用一棵有 n个结点（关键字序列）的完全二叉树表示第十章 内部排序第 44页树形选择排序 （ 又称锦标赛排序 ）
选择排序?
设初始序列为,(49,38,65,97,76,13,27,49)
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
1
3
27 49
← 关键字最小者
← 待排序列在输出最小关键字 (根 )之后，根据关系的可传递性，欲选出次最小关键字,仅需将叶结点中最小关键字 (13)改为无穷大,?”，然后从该叶结点开始和其左（或右）兄弟关键字比较，修改从叶子结点到根的路径上各结点的关键字,则根结点的关键字即为次最小关键字。
第十章 内部排序第 45页
1
3
树形选择排序 （ 又称锦标赛排序 ）
选择排序?
输出序列为,13
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
27 49
用?替换 关键字最小者 13
修改该叶结点到根的比较结果
7
6
27
2
7
← 次关键字最小由于含有 n 个叶结点的完全二叉树深应为? l o g 2 n? +1,则在树形选择中，除最小关键字之外，每选择一个次小关键字仅需进行 n2lo g 次比较，因此，其时间复杂性为 ).lo g( 2 nnO?
第十章 内部排序第 46页
1
3
树形选择排序 （ 又称锦标赛排序 ）
选择排序?
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
27 49?
7
6
27
2
7
但是这种排序方法尚有 辅助存贮空间较多和“最大值”进行多余比较 等缺点。为了弥补,J.Willioms在 1964年提出了另一种形式的选择排序 ——堆排序 。
时间复杂性为 ).lo g( 2 nnO?
第十章 内部排序第 47页堆排序 （ heap sort）
选择排序?
堆的定义,n个元素的序列当且仅当满足以下关系时，称之为堆。
12
2
ii
ii
kk
kk
或 )2,,2,1(
12
2
ni
kk
kk
ii
ii?
堆实际上是一种完全二叉树结点的层次序列，此完全二叉树的每一个结点对应一个关键码，根结点对应 k1。
堆的特性在此完全二叉树里解释为：
完全二叉树中任一结点的关键码值都小于等于（或大于等于）
它的子女结点的关键码值。
根 (k1)是完全二叉树中关键码值最小的结点。
若在输出堆的最小值后，让剩余 n － 1 个元素的序列重又建成一个堆，则得到 n -1 个元素中的次小值，为此反复进行得到一个有序序列，这个过程称为堆排序。
堆排序：
第十章 内部排序第 48页堆排序 （ heap sort）
实现堆排序需要解决两个问题：
(1) 如何由一个无序序列建成一个堆？ （建堆）
(2) 如何在输出堆顶元素之后，调整剩余元素成为一个新堆？ （调整）
13
38 27
49 76 65 49
97
即把初始序列为,(49,38,65,97,76,13,27,49)构成如下完全二叉树不需附加空间
输出堆顶元素之后，以堆中最后一个元素替代之；
以堆顶元素和其左右孩子结点的值比较，将堆顶和最小孩子交换；
参照上一步调整子树的堆，直至叶子结点。
第十章 内部排序第 49页堆排序 （ heap sort）
(2) 如何在输出堆顶元素之后，调整剩余元素成为一个新堆？ （调整）
13
38 27
49 76 65 49
97
输出堆顶元素之后，以堆中最后一个元素替代之；
13
97
以堆顶元素和其左右孩子结点的值比较，将堆顶和最小孩子交换；
27
97
参照上一步调整子树的堆，直至叶子结点。
49
97
这个自堆顶至叶子的调整过程为“筛选”
第十章 内部排序第 50页堆排序 （ heap sort）
其算法如下：
void HeapAdjust( SqList &h,int s,int m );
//堆调整，在 h.r[s..m]中，除 h.r[s].key关键字外均满足堆定义。函数将调整 h.r[s]的关键字，使 h.r[s..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( !( rc.key < h.r[j].key )) break;
h.r[s] = h.r[j]; s = j;
}
h.r[s] = rc;
}
第十章 内部排序第 51页堆排序 （ heap sort）
建堆就是从一个无序序列到建堆的过程就是一个反复,筛选,的过程若将此序列看成是一个完全二叉树，则最后一个非终端结点是第?
2
n
个元素，由此“筛选”只需从第?
2
n
个元素开始,
至第 1 个元素。
49
38 65
97 76 13 27
49
2
n 元素 49
97
2
n -1 元素13
65
2
n -2 元素根元素13
49
49
27
第十章 内部排序第 52页堆排序 （ heap sort）
建堆排序堆排序
void HeapSort( SqList &h )
{ for( i = h.length / 2; i > 0; i-- )
HeapAdjust( h,i,h.length );
for( i = h.length; i > 1; i-- )
{ h.r[1]? h.r[i];
HeapAdjust( h,1,i-1 );
}
}
排序时，调整堆 n-1趟，
堆的大小逐趟缩小，结点数分别为 n-1,n-2,…,2,1。
堆的高度逐趟降低，分别为?Log2(n-1)?+1,?Log2(n-2)?+1,…,
Log2(2)?+1,1。
每趟比较的次数分别为 2?Log2(n-1)?,2?Log2(n-2)?,…,2,0
第十章 内部排序第 53页堆排序 （ heap sort）
算法分析：
(1) 堆排序需要时间耗费在建初始堆和调整新堆时进行的反复“筛选”上。
建堆时不超过 4n，调整建新堆时调用 HeapAdjust过程 n－ 1次，
总共进行的比较次数不超过
nnnn 2222 l o g22l o g)2(l o g)1(l o g2
堆排序最坏情况下时间复杂性为 )l o g( 2 nnO? 空间复杂性为 O ( 1 ),
(2) 堆排序不适于较小的序列排序,n很大时较有效。
(3) 堆排序不稳定。
第十章 内部排序第 54页示例,初始关键字,[ 4 9 ] [ 3 8 ] [ 6 5 ] [ 9 7 ] [ 7 6 ] [ 1 3 ] [ 2 7 ]
一趟归并,[ 3 8 4 9 ] [ 6 5 9 7 ] [ 1 3 7 6 ] [ 2 7 ]
二趟归并,[ 3 8 4 9 6 5 9 7 ] [ 1 3 2 7 7 6 ]
三趟归并：
辅助空间假设初始序列有 n 个记录，则可看成是 n 个有序的子序列，每个序列的长度为 1,然后两两归并，得到
2
n
个长度为 2 或 1 的有序子序列，
再两两归并，，如此重复，直到得到一个长度为 n 的有序序列为止，
这种排序方法称为 2 —路归并排序。
归并排序?
基本思想,将两个或两个以上的有序表组合成一个新的有序表。
具体作法：
j?i? j? j?i? i? i? j?i?
13 27 38 49 65 76 97
第十章 内部排序第 55页归并排序?
算法描述：
两组归并
void merge(RecType Sr[],RecType Tr[],int i,int m,int n )
{//Sr[i..m]和 Sr[m+1..n]分别按关键字有序，现将它们归并为一个有序序列并存放在 Tr[i..n]中
for( j = m+1,k = 1; i <= m && j <= n; k++ )
{
if(( Sr[i].key <= Sr[j].key ) { Tr[k] = Sr[i]; i++ };
else
{ Tr[k] = Sr[j]; j++ }
}
if( i≤m ) Tr[k..n] = Sr[i..m];
if( j≤n ) Tr[k..n] = Sr[ j..n];
}
比较的次数 <=m+n
赋值的次数 =m+n
第十章 内部排序第 56页归并排序?
算法描述：
归并排序的递归算法
void msort( RecType Sr[],RecType &Tr1[],int s,int t )
{//对 r[s..t]中记录进行归并排序
if( s == t ) Tr1[s] = Sr[s];
else
{ m = ( s + t ) / 2;
msort( Sr,Tr2,s,m );
msort( Sr,Tr2,m +1,t);
merge( Tr2,Tr1,s,m,t );
}
}
Void MergeSort( SqList &L)
{ msort( L.r,L.r,1,L.length );
}
第十章 内部排序第 57页
n个记录要进行多少趟归并？
要归并?Log2n? 趟。
每趟比较次数 <=n,赋值次数 =n。
归并排序的算法分析总时间复杂性为 O(nlog2n),空间复杂性为 O(n)。
归并排序是稳定的。
示例,初始关键字,[ 4 9 ] [ 3 8 ] [ 6 5 ] [ 9 7 ] [ 7 6 ] [ 1 3 ] [ 2 7 ]
一趟归并,[ 3 8 4 9 ] [ 6 5 9 7 ] [ 1 3 7 6 ] [ 2 7 ]
二趟归并,[ 3 8 4 9 6 5 9 7 ] [ 1 3 2 7 7 6 ]
三趟归并：
j?i? j? j?i? i? i? j?i?
[13 27 38 49 65 76 97]
一棵有 n个树叶的“倒”的完全二叉树，
深度为?Log2n?+1。
第十章 内部排序第 58页概述 ——多关键字的排序基数排序示例,已知扑克牌中 52张牌面的次序关系为：
2<?3<..<?A<?2<?3<..<?A
<?2<?3<..<?A<?2<?3<..<?A
每一张牌面有两个关键字：
花色（?,?,?,?）和面值（ 2,3,…,K,A），且花色的地位高于面值。现要对扑克牌进行整理。
这是一个多关键字的排序问题。
一般情况下，假设有 n 个记录的序列 },,,(
21 n
RRR? 且每个记录
i
R 中含有 d 个关键字
d
iii
KKK,,,
21
,则称序列对关键字有序递增是指：对于序列中任意两个记录 iR 和 )1( njiR j 都满足下列有序关系,
d
jjj
d
iii
KKKKKK,,,,,,
2121
其中
1
K 称为最高位关键字，
d
K 称为最低位关键字。
第十章 内部排序第 59页概述 ——多关键字的排序为实现多关键字排序,通常有两种方法：
如理牌示例中，先按花色，再按面值。
1)最高位优先（ MSD法）
先按最高位关键字排序，将序列分成若干子序列，再按次高位关键字排序分成若干更小的子序列，依次重复，最后得到有序序列。
2)最低位优先（ LSD法）
从最低位关键字开始排序，然后再对高一位排序，依次重复，
直到对最高位排序。
如理牌示例中，先按面值，再按花色。
第十章 内部排序第 60页概述 ——多关键字的排序说 明,
以整数关键字为例,若采用最高位优先,则首先按最高位分配,假设关键字取值 0~999之间,则可将 0~99的放在一个盒子中,
100~199的放在另一个盒子中,…,900~999放在最后一个盒子,
然后再将每个盒子中的关键字排序 。 这种分配方法实际上就是把一个整数看成是三位数字组合的复合关键字 。
(1)当关键字为多字段时，基数排序是一种很自然的方法，一般说来，最低位优先法要比最高位优先法简单，因为前者是从头到尾进行若干次分配与收集，执行的次数取决于构成关键字成分的多少；而后者则要分配以后处理各子集的排序问题，这通常是一个递归过程。
(2)当关键字为一简单的字段时，也可以采用分配排序的思想。
快速排序某种意义上就是可看成一种最高位优先的分配排序，
因为执行快速排序每趟都将关键字分成两组（两个盒子），然后递归处理排序问题。
第十章 内部排序第 61页基数排序其中 r称为基数 。 基数的选择和关键字的分解法,因关键字的类型而异 。 关键字为十进制整数时,最自然的取法是 r 为 10
（ 0~9）,当关键字为字符串时,可取 r =26（ A~Z） 。
基本思想,把每一个关键字看成是一个 d元组：
排序时先按 Kdi的值从小到大将记录分配到 r个盒子中，然后依次收集这些记录，再按 Kid-1的值分配到 r个盒子中，如此反复，直到对 K1i分配后收集起来的序列，便是完全排序的序列。
),,,( 21 diiii KKKK
第十章 内部排序第 62页示例 设初始关键字序列为 {278,109,063,930,589,184，
505,269,008,083}。取 r=10,d=3,c1=0,cdr=9。以 10个链队列表示 10个箱子,f [i] 和 e[i] 分别为第 i(0≤i≤9) 个队列的头指针和尾指针。
链式基数排序过程示例如下
278 109 063 930 589 184 505 269 008 083
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
930 063 184 505 278 109
083 008 589
269
f [0] f [1] f [2] f [3] f [4] f [5] f [6] f [7] f [8] f [9]
(b)
第一趟分配之后
930 063 083 184 505 278 008 109 589 269
(c) 第一趟收集之后
(a) 初始状态第十章 内部排序第 63页链式基数排序的数据类型定义（以静态链表作存储结构）
#define MAX_NUM_OF_KEY 8 //关键字项数最大值
#define RADIX 10 //关键字基数，十进制
#define MAX_SPACE 10000
typedef struct {
KeysType Keys[MAX_NUM_OF_KEY]; //关键字
InfoType otherItems;
int next;
} SLCell;
typedef struct{
SLCell r[MAX_SPACE]; //静态链表,r[0]为头结点
int keynum; //关键字个数
int recnum; //静态链表长度
}SLList; //静态链表类型
typedef int ArrType[RADIX];
链式基数排序第十章 内部排序第 64页链式基数排序中一趟分配的算法描述
void distribute(SLCell &r,int i,ArrType &f,ArrType &e )
{//静态链表 L的 r 域中的记录按 (key[0],···,key[i-1]) 有序。本算法按第 i 位关键字 key[i] 建立子表，同一子表中记录的 key[i] 相同,f
和 e 分别指向各子表中第一个和最后一个记录。
for( j = 0; j < RADIX,j++ )
f[j]:=0; //子表初始化为空表
for( p = r[0].next; p; p = r[p].next )
{ j = ord( r[p].key[i] ); //提取记录中第 i 个关键字映射到
//[0..RADIX-1]
if( f[ j] == 0 ) f[ j] = p;
else r[e[j]].next = p;
e[j] = p; //将 p 所指结点插入第 j 个子表中
}
} 算法 10.15
链式基数排序分配工作需 O(n)
的时间第十章 内部排序第 65页链式基数排序中一趟收集的算法描述
void collect ( SLCell &r,int I,ArrType f,ArrType e )
//本算法按 key[i] 自小至大将 f[0..RADIX-1] 所指各子表链接成一个链表,e[0..RADIX-1] 为相应各子表的尾指针。
{for( j = 0; !f[j]; j = succ(j)); //找一个非空子表,succ 为求后继函数
r[0].next = f[j]; t = e[j];//r[0].next指向第一个非空子表中第一个结点
while( j < RADIX )
{ for( j = succ(j); j < RADIX-1 && !f[j]; j = succ(j));
//找下一个非空子表
if( f[j] )
{ r[t].next = f[j]; t = e[j] } //链接两个非空子表
};
r[t].next = 0 //t 指向最后一个非空子表中的最后一个结点
} 算法 10.16
链式基数排序收集需要 O(r)的时间第十章 内部排序第 66页链式基数排序的算法描述
void radixsort (SLList &L )
{//n 个记录存放在静态链表的数据域中，执行本算法进行基数排序后，链表中的记录按关键字自小至大相链。
for( i = 0; i < L.recnum; i++ )
L.r[i].next = i+1;
L.r[n].next = 0; //链表初始化
for( i = 0; i < L.keynum; i++ )
{ distribute( L.r,i,,f,e ); //第 i 趟分配
collect (L.r,i,f,e ) //第 i 趟收集
}
} 算法 10.17
链式基数排序第十章 内部排序第 67页链式基数排序链式基数排序的算法分析在链式基数排序中，没有进行关键字的比较和记录的移动，
而只是顺链扫描表和进行指针赋值，所以排序的时间主要耗费在修改指针上。
将 r 初始化成一个静态链表的时间是 O(n)。
在每一趟排序中，分配时间是 O(n)； 收集的时间是 O(rd)；
所以链式基数排序时间复杂度是 O(d*(rd+n))。显然，若 d 是常数,rd 是常数，基数排序的时间复杂度都是 O(n)，
但必须指出，当 n 较小,d 较大时，基数排序并非合适。只有当
n 较大,d 较小时，特别是记录的信息量较大时，基数排序最为有效。 在基数排序中，每一个记录中增加了一个 next 域，另外还增加 f,e 两个数组。
第十章 内部排序第 68页内部排序方法的比较和选择选取排序方法时需考虑的因素,
(1) 待排序的记录数目 n；
(2) 记录本身信息量的大小；
(3) 关键字的结构及其分布情形；
(4) 对排序稳定性的要求；
(5) 语言工具的条件；
(6) 辅助空间的大小。等等排序方法 平均时间 最坏情况 辅助存储简单排序 O ( n
2
) O ( n
2
) O ( 1)
快速排序 O ( nl ogn ) O ( n
2
) O ( l ogn )
堆 排 序 O ( nl ogn ) O ( nl ogn ) O ( 1 )
归并排序 O ( nl ogn ) O ( nl ogn ) O ( n )
基数排序 O ( d ( n + rd )) O ( d ( n + rd )) O ( rd )
下表给出各种排序方法的主要性能第十章 内部排序第 69页
(2) 若 n 较大，则应采用时间复杂度为 O(nlogn) 的排序方法，如快速排序、堆排序或归并排序等。快速排序是目前基于比较的内部排序中被认为是最好的方法。当待排序的关键字是随机分布时，快速排序的平均时间最短，但堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
内部排序方法的比较和选择?
内部排序方法的比较和选择
(1) 若 n 较小，则可选用直接插入排序或直接选择排序。
(3) 基数排序的时间复杂度也可写成 O(d·n)，它最适合于 n 值很大而关键字较小的序列。
(4) 从方法的稳定性来比较，基数排序是稳定的内部排序方法，所有时间复杂度为 O(n2) 的简单排序法也是稳定的；然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。
由于大多数情况下排序是按记录的主关健字进行的，故所选用的排序方法是否稳定无关紧要。
第十章 内部排序第 70页第十章 内部排序 小结基本内容
五类内部排序方法（插入排序、交换排序、选择排序、归并排序、基数排序）的基本思想、排序过程和实现算法
各类排序算法的时间复杂度分析
各种排序方法的比较和选择学习要点
深刻理解各种内部排序方法的基本思想及其特点
熟悉各种排序方法的排序过程
理解各种排序方法的算法实现及时间复杂度分析第十章 内部排序第 71页复 习一,全面复习二,以教材为主基本概念基本算法基本应用
ADT
类 C 描述一般的时空效率分析三,以课堂讲授内容为准四,课外作业、课堂小练习、上机作业第十章 内部排序第 72页
第十章 内部排序第十章 内部排序第 2页第十章 内部排序内容和要求排序及有关的概念，直接插入排序、二分法插入排序、表插入排序,shell排序，直接选择排序、树形选择排序、堆排序、冒泡排序和快速排序、基数排序、归并排序。
要求通过学习，掌握排序的各种方法，为解决实际问题奠定理论基础的技术基础。了解排序和排序码的概念，
熟悉 直接插入排序、二分法插入排序、表插入排序
,Shell排序的方法和时空复杂性；
掌握 堆排序、快速排序、基数排序、归并排序的基本思路，排序方法，算法的主要步骤和时空复杂性；
知道 shell 排序和树形选择排序方法 。
第十章 内部排序第 3页概 述如何对一大批按关键字无序的数据元素或记录，高效率地将它们重新排列成一个按关键字有序的序列，是计算机应用中的重要课题之一。
可以假定被排序的对象是由一组记录组成的文件，而记录则由若干个数据项
（或字段、域）组成，其中有一项可用来标识一个记录，称为 关键字,它具关键字值。关键字是排序操作的依据。
第十章 内部排序第 4页定义 1,假设含 n 个记录的序列为
{R1,R2,···,Rn} (10-1)
其相应的关键字序列为
{K1,K2,···,Kn}
需确定 1,2,··,n 的一种排列 P1,P2,···,Pn,使其相应的关键字满足如下的非递减（或非递增）关系
Kp1≤Kp2 ≤··· ≤ Kpn (10-2)
即使式 (10-1) 的序列成为一个按关键字有序的序列
{Rp1,Rp2,···,Rpn } (10-3)
这样一种操作称为排序。
概 述?
显然，当待排记录的关键字均不相同时，则排序的结果是唯一的，否则排序的结果不一定唯一。特别地,按主关键字进行排序，其排序的结果是唯一的 。而若按次关键字进行排序，结果不一定唯一。
第十章 内部排序第 5页定义 2,如果待排序的文件中，存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是 稳定的 ；
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。
定义 3,在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换,则称为内部排序，简称内排序； 反之，若排序过程中要进行数据的内、外存交换,则称之为外部排序，简称外排序 。
概 述?
第十章 内部排序第 6页概 述?
各种排序方法可以按照不同的原则加以分类。
内部排序方法的分类：
一、按所用策略进行分类
(1) 插入排序
(2) 交换排序
(3) 选择排序
(4) 归并排序
(5) 计数排序二、按所需工作量进行分类
(1) 简单的排序方法 O(n2)
(2) 先进的排序方法 O(nlogn)
(3) 基数排序 O(d?n)
第十章 内部排序第 7页在排序的过程中需进行的 两种基本操作,
(1) 比较两个关键字的大小 ；
(2) 将记录从一个位置移动至另一个位置。
前一个操作对大多数排序方法来说都是必要的，而后一种操作可以通过改变记录的存储方式来予以避免。
概 述?
排序的时间开销是算法好坏的最重要的标志。 排序的时间开销主要可以用算法执行中 关键字的比较次数 和记录的移动次数 来衡量。
第十章 内部排序第 8页概 述?
设待排记录的数据类型为
#define MAX_SIZE 20
typedef int KeyType
typedef struct {
KeyType key;
InfoType otherInfo;
} RecType;
typedef struct {
RecType r[MAX_SIZE + 1];
int Length;
}SqList;
三种存储方式：
（ 1）待排序记录存放在地址连续的存储单元上。
（ 2）待排序记录存以静态链表存储，记录间的次序由指针指示。
（ 3）待排序记录存放在在连续存储单元中，另设指向各个记录地址的指针向量。
第十章 内部排序第 9页插 入 排 序插入排序的基本思想是,每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的表或文件中的适当位置，直到全部插入完为止。
直接插入排序基本操作是 将一个记录插入到已排好序的有序表中，
从而得到一个新的、记录数增 1的有序表。
直接插入排序 分趟 进行,一般情况下，第 i 趟直接插入排序的操作为,在含在 i-1 个记录的有序子序列
r[1..i-1] 中，首先查找 r[i]的插入位置 j,使得
r[j].key? r[i].key< r[j+1].key (0? j<i)
在 r[j]之后 插入一个记录 r[i],得到含有 i 个记录的有序子序列 r[1..i] 。
第十章 内部排序第 10页示例 1 设待排关键字集合为
{49,38,65,97,76,13,27,49}
[初始关键字 ] (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)
↑监视哨 图 10.1 直接插入排序示例直接插入排序第十章 内部排序第 11页直接插入排序算法描述（ n 个记录，共进行 n-1 趟插入）
straisort( SqList &l )
//对 r[1..n] 进行直接插入排序，执行本算法后,r[1..n]
中的记录按关键字非递减有序排列
{ for( i = 2; i <= l.Length; i++ )
if( l.r[i].key < l.r[i-1].key )
{ 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];
}
}
直接插入排序第十章 内部排序第 12页
(1) 若初始序列按关键字递增有序（简称正序），则最小比较次数最小移动次数 0
直接插入排序算法分析直接插入排序算法由两重循环组成，外循环表示要进行 n-1
趟插入排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。
直接插入排序是稳定的排序方法 。
(2) 若初始文件按关键字递减有序（简称逆序或反序），则最大比较次数最小移动次数
(3) 若初始文件按关键字随机排列，则关键字的比较次数和移动次数均为 (n2)/4
故直接插入排序算法的时间复杂度为 O(n2)。空间复杂度为 O(1).
第十章 内部排序第 13页在直接插入排序的一趟 (第 i 趟 ) 算法中，搜索操作可由在区间
[1,i-1] 上进行折半查找来实现 。如此进行的插入排序称为折半插入排序 (Binary Insertion Sort)。
折半插入排序
BInsertSort( SqList &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( l.r[0].key < l.r[m].key ) hight = m – 1;
else low = m + 1;
} //while
for( j = i – 1; j >= high + 1; j++ ) r[j+1] = r[j]; //记录后移
l.r[high+1] = r[0]; //插入 r[i]
} //算法 10.4
折半插入排序的时间复杂度仍为 O(n2)。减少了比较次数，其排序方法是稳定的。
第十章 内部排序第 14页
2-路插入排序在折半插入排序基础上的一种改进算法,其目的是减少排序过程中移动记录的次数，但为此需要 n 个记录的辅助空间。
算法思想,另设一个和 L 同类型的数组 d，将它看成是一个循环向量，并设两个指针 first 和 final 分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。首先将 r[1] 赋值给 d[1]，并将 d[1] 看成是在排好序的序列中处于中间位置的记录，然后从 r
中第 2个记录起依次插入到 d[1] 之前或之后的有序序列中。
第十章 内部排序第 15页示例 2 设待排序关键字集合同示例 1，采用 2-路插入排序算法
[初始关键字 ] 49 38 65 97 76 13 27 49
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
图 10.2 2-路插入排序示例第十章 内部排序第 16页在 2-路插入排序中，记录移动的次数会减少
，但是不能绝对避免移动记录。
在通常情况下，移动记录的次数约为 n2/8。
极端情况下，当 r[1] 是待排序记录中关键字最小或最大的记录时,2-路插入排序就完全失去它的优越性。
如希望不移动记录，只有改变存储结构，采用表插入排序。
2-路插入排序第十章 内部排序第 17页表插入排序算法思想,以静态链表作为存储结构（ 用数组描述的链表，有整数指示域）。 在插入 Ri 时,R1到 Ri-1
已用指针按关键字不减次序链接起来，这时采用顺序比较方法找到 Ri 应该插入的位置，然后作链表的插入，使得到从 R1—Ri 的已排序的链表。如此反复，
直到把 Rn 插入链表，排序过程结束。
为使插入方便，在数组中多设一个下标为 0 的分量作为表头结点，并令表头记录的关键字为最大整数
maxint。排序开始时，先令表头结点和第一个记录结点组成一个循环链表，然后从 i=2 起，依次将第 i 个结点插入链表。
表插入排序解决了在排序过程中不移动记录，但比较次数不变。故其算法的时间复杂度仍是 O(n2).
第十章 内部排序第 18页用于表插入排序的静态链表数据结构
#define SIZE 100
typedef struct{
RecType rc; //关键字,Info
int next
} SLNode;
typedef struct{
SLNode r[SIZE];
int length;
}SLinkListType;
示例 3 设待排序关键字集合同示例 1，采用表插入排序算法表插入排序第十章 内部排序第 19页
1 2 3 4 5 6 7 80
49 38 65 97 76 13 27 49maxint
0 - - - - - - -1初始
49 38 65 97 76 13 27 49maxint
0 1 - - - - - -2i=2
49 38 65 97 76 13 27 49maxint
3 1 0 - - - - -2i=3
49 38 65 97 76 13 27 49maxint
3 1 4 0 - - - -2i=4
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 - - -2i=5
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 2 - -6i=6
49 38 65 97 76 13 27 49maxint
3 1 5 0 4 7 2 -6i=7
49 38 65 97 76 13 27 49maxint
8 1 5 0 4 7 2 36i=8
第十章 内部排序第 20页表插入排序的结果只是求得一个有序链表，为了能应用有序表的折半查找，尚需对记录进行重新排列。
表插入排序重排记录的做法是,顺序扫描有序链表，将链表中第
i 个结点移动至第 i 个分量中。
若
SLinkListType rsl;
则一般情况下,若第 i 个最小关键字的结点是数组中下标为 p 且 p>i 的分量，则互换 rs1[i] 和 rs1[p]，且令
rs1[i] 中指针域的值改为 p； 由于此时数组中所有小于 i 的分量中已是“到位”的记录，则当 p<i 时，应顺链继续查找直到 p≥i 为止。
第十章 内部排序第 21页
1 2 3 4 5 6 7 80
49 38 65 97 76 13 27 49maxint
8 1 5 0 4 7 2 36初始
13 38 65 97 76 49 27 49maxint
(6) 1 5 0 4 8 2 37
i=1
P=6
13 27 65 97 76 49 38 49maxint
(6) (7) 5 0 4 8 1 32
i=2
P=7
13 27 38 97 76 49 65 49maxint
(6) (7) (7) 0 4 8 5 31
i=3
P=(2)=7
13 27 38 49 76 97 65 49maxint
(6) (7) (7) (6) 4 0 5 38
i=4
P=(1)
6
13 27 38 49 49 97 65 76maxint
(6) (7) (7) (6) (8) 0 5 43
i=5
P=8
13 27 38 49 49 65 97 76maxint
(6) (7) (7) (6) (8) (7) 0 45
i=6
P=(3)
7
13 27 38 49 49 65 76 97maxint
(6) (7) (7) (6) (8) (7) (8) 04
i=7
P=(5)
8
第十章 内部排序第 22页表插入排序
void Arrange( SqLinkType &sl )
{ p = sl.r[0].next;
for( i = 1; i < sl.length; i++ )
{ while( p < i ) p = sl.r[p].next;
q = sl.r[p].next;
if( p != i )
{ sl.r[p] <－ > sl.r[i];
sl.r[i].next = p;
}
p = q;
}
}
算法如下：
在重排过程中，最坏情况是每个记录到位都进行一次交换，因此，重排最多允许有 2(n-1)次记录移动，不增加排序时间复杂度。
第十章 内部排序第 23页希尔排序希尔排序 (Shell`s Method) 又称缩小增量排序
(Diminishing Increment Sort) 。是由 D.L.Shell 在 1959年提出来的。 效率有较大改进。
它的基本作法是,先取定一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组，所有距离为 d1 倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量 d2<d1 重复上述分组和排序，直至所取的增量 dt=1(dt<dt-1<··<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
希尔排序的基本思想是,先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
第十章 内部排序第 24页示例 5 设初始关键字序列集合为 {49,38,65,97
,76,13,27,49,55,04}，则按增量（即步长）
分别取 5,3,1进行希尔排序，三趟排序结果如下所示初始关键字 49 38 65 97 76 13 27 49 55 04
5步分类 13 27 49 55 04 49 38 65 97 76
3步分类 13 04 49 38 27 49 55 65 97 76
1步分类 04 13 27 38 49 49 55 65 76 97
希尔排序的一个特点是,子序列的构成不是简单地
“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。 关键字较小的记录不是一步一步地往前挪动
，而是跳跃式地往前移，从而使得在进行最后一趟增量为 1的插入排序时,序列已基本有序,只要作记录的少量比较和移动即可完成排序 。
第十章 内部排序第 25页希尔排序的算法描述
void shellsort ( SqList &L,int dlta[],int t )
{//本算法对 l.r[1..n] 中记录进行 t 趟希尔排序。 d[1]<n,d[2],··,d[t]=1
为各趟排序的增量序列
for( k =1; k <= t; k++ )
ShellInsert( L,dlta[k] );
} //shellsort 算法 10.5
其中 ShellInsert 为一趟（第 k 趟）希尔排序的算法。
void ShellInsert( SqList &L,int dk )
{ //本算法进行一趟希尔排序,dk 为增量
for( i = dk + 1; i <= L.length; i++ )
if( 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]; //插入
}
} //shellposs 算法 10.4
第十章 内部排序第 26页说明
(1) 在希尔排序算法中，如何选择增量序列才能产生最好的排序效果，是一个困难的数学问题，至今没有得到解决。增量序列可以有各种取法。
Knuth 给出：当 n 在某个特定范围内，希尔排序所需的比较和移动次数约为 n1.3，当 n→∞ 时，可减少到
n(log2n)2.
(2) 希尔排序的时间性能优于直接插入排序。在希尔排序开始时增量较大，分组较多，每组的记录数目少
，故各组内直接插入较快，后来增量 di 逐渐缩小，
分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按 di-1 作为距离排过序，使文件较接近于有序状态。因此，希尔排序在效率上较直接插入排序有较大的改进。
希尔排序第十章 内部排序第 27页插入排序总结
直接插入排序
折半插入排序
– 减少了比较次数 –采用折半查找
2路插入排序
– 减少了记录移动的次数。
表插入排序
– 记录不移动，利用静态链表完成排序。如需要按次序排序，则需要 2(n-1)次移动。
Shell排序
–,跳跃式”的插入排序。目的尽量使排序记录“
基本有序”从而减少比较和移动的次数。
第十章 内部排序第 28页交 换 排 序一类藉助,交换” 进行排序的方法。交换排序的基本思想是,两两比较待排记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录时为止。
两类常用的交换排序,起泡排序和快速排序 。
起泡排序的算法思想很简单,两两比较，随时交换。它亦是分一趟一趟地进行的。若设想把待排序记录数组 R[1..n] 垂直竖立，则按自上而下或从下往上扫描，可视作“石块下沉”或“气泡上浮”的操作过程。
直接交换排序 ——起泡排序第十章 内部排序第 29页示例 1 设初始关键字序列为 {49,38,65,97,76,13，
27,49} 如下所示是自上而下扫描的起泡排序示例
49 38 38 38 38 13 13 13
38 49 49 49 13 27 27 27
65 65 65 13 27 38 38 38
97 76 13 27 49 49 49 49
76 13 27 49 49 49 49 49
13 27 49 65 65 65 65 65
27 49 76 76 76 76 76 76
49 97 97 97 97 97 97 97
初 第 第 第 第 第 第 第始 一 二 三 四 五 六 七关 趟 趟 趟 趟 趟 趟 趟键 排 排 排 排 排 排 排字 序 序 序 序 序 序 序后 后 后 后 后 后 后图 10.6 自上而下扫描的起泡排序示例直接交换排序 ——起泡排序第十章 内部排序第 30页注,判别起泡排序结束的条件：在一趟排序过程中没有进行过交换记录的操作。
起泡排序的算法描述
void bubblesort ( SqList &L )
{ for( i = 1; i <= n-1; i++ ) //最多做 n-1 趟排序
{ noswap = ture; //置未交换的标志
for( j = n-1; j <= i; j-- ) //从底部往上扫描
if( L.r[j+1].key < L.r[j].key ) //交换记录
{ r[j+1]? r[j]; noswap = false };
if( noswap )
return //本趟排序中未发生交换终止算法
}
} //bubblesort
直接交换排序 ——起泡排序第十章 内部排序第 31页起泡排序的算法分析：
(1) 若数组的初始状态是正序的，则一趟扫描就可完成排序，
关键字的比较次数为 n-1，且没有记录移动。也就是说，起泡排序在最好地情况下，时间复杂度是 O(n).
直接交换排序 ——起泡排序
(2) 若初始数组是反序的，则需要进行 n-1 趟排序，每趟排序要进行 n-i 次关键字的比较 (1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。
第十章 内部排序第 32页快速排序快速排序也称分区交换排序，是对起泡排序的一种改进。
基本思想,通过一趟排序将待排记录分割成独立的两部分，
其中一部分记录的关键字均比另一部分关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序。
首先任取一个记录（通常可选第一个记录） 作为标准
（枢轴、支点,pivot）。
然后排列其余记录，将所有关键字 较它小 的记录都安置在它的位置 之前,所有关键字 不小于它 的记录安置在它之后 。
第十章 内部排序第 33页快速排序怎样进行一次划分？
具体方法：
1,附设两个指针 low和 high，分别指向序列的左右两端，设标准关键字为左端第一个，用附加记录 rpivot保存 ;
2,high就地开始，向左搜索，找到第一个关键字小于 x的记录；
low,high始终应保持,low<=high,即 low,high从两端往中间搜索
3,把 high所指记录赋给 i所指位置 ;
4,low就地开始，向右搜索，找到第一个关键字大于 x的记录；
low,high始终应保持,low<=high,即 low,high从两端往中间搜索
5,把 i所指记录赋给 j所指位置 ;
6,重复 2到 5，直到 low=high，把附加记录 rp（支点值）赋给 i位置。
第十章 内部排序第 34页快速排序一趟快速排序示例,设初始关键字为 (49,38,65,97,76,13,27,49)
初始关键字,49 38 65 97 76 13 27 49
支点 l.r[1ow].key =49 ↑low ↑high
high往左搜索,49 38 65 97 76 13 27 49
↑low ↑high↑high
r[low] = r[high],27 38 65 97 76 13 27 49
↑low ↑high
low 往右搜索,27 38 65 97 76 13 27 49
↑low ↑high↑low
r[high] = r[low],27 38 65 97 76 13 65 49
↑low ↑high
6,重复 2到 5，直到 low=high，把附加记录（支点值）赋给 low位置。
完成一趟排序,27 38 13 49 76 97 65 49
low↑high
第十章 内部排序第 35页算法如下：
int Partition( SqList &L,int Low,int High )
{
L.r[0] = L.r[low]; pivotkey = L.r[low].key;
while( Low < High )
{ while( Low < High && L.r[j].key ≥ pivotkey ) j--;
L.r[low] = L.r[High];
while( Low < High && L.r[i].key ≤ pivotkey ) i++;
L.r[High] = L.r[Low];
}
L.r[i] = L.r[0];
return Low;
}
快速排序?
这样排序能否稳定？ 不稳定原则上象这种跳跃式交换的排序方法都不稳定第十章 内部排序第 36页整个快速排序过程可递归进行 （ 在一趟快速排序基础上 ）,快速排序算法：
qsort( SqList &L,int Low,int High )
{ if( Low < High )
{ pivotLoc = Partition( L,Low,High );
qsort( L,Low,pivotLoc - 1);
qsort( L,pivotLoc + 1,High );
}
} //qsort
快速排序?
Void QuickSort( SqList &L )
{ Qsort( L,1,L.length );
}
第十章 内部排序第 37页分别进行块排序,{13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束结束排序结果,13 27 38 49 49 65 76 97
示例：接一趟快速排序结果：
初始,49 38 65 97 76 13 27 49
一次划分之后,{27 38 13} 49 {76 97 65 49}
快速排序?
？这种排序比起泡排序有什么改进，有什么代价一趟排序后，都只把一个记录安排到正确的位置,但快速排序这个位置还起了分隔作用，为下次排序节省了时间。这个位置越居中效果越好。最坏情况是这个位置居于一端，与起泡排序无异。
代价：每趟排序需要一个附加的记录空间。
整个排序因使用递归，还需要栈空间。
第十章 内部排序第 38页算法分析,假定有 n个记录待排快速排序?
(1) 最好的情况,如果第一次选定的就把 n个记录分成 大小相同的两个子块,第一趟排序已有一个记录安排在正确的位置，其比较次数为 n，故所需时间为 O(n)或 Cn（ C为常数）
设对 n 个记录排序时间为 T ( n ),则有：
2
2)( nTCnnT
)l o g()1(l o g
4
42
4
2
2
2
2
2)(
22
nnOnTcnn
n
Tcn
n
T
cn
cn
n
TcnnT
(2) 最坏情况,当初始序列按关键有序或基本有序时，快速排序将蜕化为超泡排序，其时间复杂性为 ).( 2nO
第十章 内部排序第 39页算法分析,假定有 n个记录待排快速排序?
(3) 一般情况：设 为平均时间,则)(nT a v g
1
0
1
)(
2
)()1(
1
)(
n
i
n
k
iTa v g
n
cn
knTa v gkTa v g
n
cnnTa v g
假定 bT a v g?)0( 和 bT a v g?)1( （ b 为某个常量），
则可证明当 )(2 cbk 和 2?n 时，
有,nnknT a v g ln)(
第十章 内部排序第 40页说明：
快速排序?
(1) 快速排序需要一个递归实现（前面各种排序方法只须一个空间）最好情况下（每一趟划分都将序列均匀分割成长度应相近的两个子序列）栈的最大深度为 Log2n+1,但最差时栈的深度为 n。
(2) 为避免蜕化为超泡排序，可改进支点记录（枢轴）的选取，
通常依“三者取中”法则来选取，即比较取三者中关键字取中值点记录为支点关键字。
,.2,].[ k e ytsrk e ysr keytr ].[
(3) 就平均性质而言，快速排序是目前被认为最快的一种内部排序方法。（同数量级排序方法相比，其常数因子 k最小）
(4) 快速排序是不稳定的排序第十章 内部排序第 41页简单选择排序选择排序?
一趟简单选择排序的操作为：
通过 n－ i次关键字间的比较，从 n－ i+1个记录中选出关键字最小的记录，并和第 i个记录交换。 重复上述过程 n－ 1次，即可完成排序。
算法如下：
void smp_selectsort( SqList &L )
{ for( i =1; i <= L.length - 1; i++ )
{ k = i;
for( j = i+1; j <= L.Length; j++ )
if( L.r[j].key < L.r[k].key ) k = j;
if( k≠i ) L.r[i]? L.r[k];
}
} //smp_selectsort
算法分析：
记录移动次数为 0~3(n－ 1),关键字的比较次数为,)1(21 nn
时间复杂性为 ).( 2nO
第十章 内部排序第 42页简单选择排序选择排序?
简单选择排序是不稳定的示例,49 38 65 97 76 27 49 13
No1,13 38 65 97 76 27 49 49
No2,13 27 65 97 76 38 49 49
No3,13 27 38 97 76 65 49 49
No4,13 27 38 49 76 65 97 49
No5,13 27 38 49 49 65 97 76
No6,13 27 38 49 49 65 97 76
No7,13 27 38 49 49 65 76 97
第十章 内部排序第 43页树形选择排序 （ 又称锦标赛排序 ）
选择排序?
简单选择排序时,为了从 n个关键字中找出最少者,需 n－ 1次比较,然后又在 n－ 1个关键字中找次最小的关键字需 n－ 2次比较 。 事实上,后面这 n－ 2次比较中允许比较可能在第一趟的 n－ 1次比较中做过,但是由于第一次比较时,这些结果没有保留下来,所以在第二趟又重复进行 。 树形选择排序可以克服这一缺点 。
具体做法,
把 n 个关键字两两进行比较，取出
2
n
个较小的关键字作为第一步比较的结果保存下来，再把这
2
n
个关键字两两比较，如此反复，一直到比较出最小的关键字为止。
这一过程可用一棵有 n个结点（关键字序列）的完全二叉树表示第十章 内部排序第 44页树形选择排序 （ 又称锦标赛排序 ）
选择排序?
设初始序列为,(49,38,65,97,76,13,27,49)
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
1
3
27 49
← 关键字最小者
← 待排序列在输出最小关键字 (根 )之后，根据关系的可传递性，欲选出次最小关键字,仅需将叶结点中最小关键字 (13)改为无穷大,?”，然后从该叶结点开始和其左（或右）兄弟关键字比较，修改从叶子结点到根的路径上各结点的关键字,则根结点的关键字即为次最小关键字。
第十章 内部排序第 45页
1
3
树形选择排序 （ 又称锦标赛排序 ）
选择排序?
输出序列为,13
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
27 49
用?替换 关键字最小者 13
修改该叶结点到根的比较结果
7
6
27
2
7
← 次关键字最小由于含有 n 个叶结点的完全二叉树深应为? l o g 2 n? +1,则在树形选择中，除最小关键字之外，每选择一个次小关键字仅需进行 n2lo g 次比较，因此，其时间复杂性为 ).lo g( 2 nnO?
第十章 内部排序第 46页
1
3
树形选择排序 （ 又称锦标赛排序 ）
选择排序?
1
3
3
8
13
3
8 65 13 27
4
9
3
8
6
5
9
7
7
6
27 49?
7
6
27
2
7
但是这种排序方法尚有 辅助存贮空间较多和“最大值”进行多余比较 等缺点。为了弥补,J.Willioms在 1964年提出了另一种形式的选择排序 ——堆排序 。
时间复杂性为 ).lo g( 2 nnO?
第十章 内部排序第 47页堆排序 （ heap sort）
选择排序?
堆的定义,n个元素的序列当且仅当满足以下关系时，称之为堆。
12
2
ii
ii
kk
kk
或 )2,,2,1(
12
2
ni
kk
kk
ii
ii?
堆实际上是一种完全二叉树结点的层次序列，此完全二叉树的每一个结点对应一个关键码，根结点对应 k1。
堆的特性在此完全二叉树里解释为：
完全二叉树中任一结点的关键码值都小于等于（或大于等于）
它的子女结点的关键码值。
根 (k1)是完全二叉树中关键码值最小的结点。
若在输出堆的最小值后，让剩余 n － 1 个元素的序列重又建成一个堆，则得到 n -1 个元素中的次小值，为此反复进行得到一个有序序列，这个过程称为堆排序。
堆排序：
第十章 内部排序第 48页堆排序 （ heap sort）
实现堆排序需要解决两个问题：
(1) 如何由一个无序序列建成一个堆？ （建堆）
(2) 如何在输出堆顶元素之后，调整剩余元素成为一个新堆？ （调整）
13
38 27
49 76 65 49
97
即把初始序列为,(49,38,65,97,76,13,27,49)构成如下完全二叉树不需附加空间
输出堆顶元素之后，以堆中最后一个元素替代之；
以堆顶元素和其左右孩子结点的值比较，将堆顶和最小孩子交换；
参照上一步调整子树的堆，直至叶子结点。
第十章 内部排序第 49页堆排序 （ heap sort）
(2) 如何在输出堆顶元素之后，调整剩余元素成为一个新堆？ （调整）
13
38 27
49 76 65 49
97
输出堆顶元素之后，以堆中最后一个元素替代之；
13
97
以堆顶元素和其左右孩子结点的值比较，将堆顶和最小孩子交换；
27
97
参照上一步调整子树的堆，直至叶子结点。
49
97
这个自堆顶至叶子的调整过程为“筛选”
第十章 内部排序第 50页堆排序 （ heap sort）
其算法如下：
void HeapAdjust( SqList &h,int s,int m );
//堆调整，在 h.r[s..m]中，除 h.r[s].key关键字外均满足堆定义。函数将调整 h.r[s]的关键字，使 h.r[s..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( !( rc.key < h.r[j].key )) break;
h.r[s] = h.r[j]; s = j;
}
h.r[s] = rc;
}
第十章 内部排序第 51页堆排序 （ heap sort）
建堆就是从一个无序序列到建堆的过程就是一个反复,筛选,的过程若将此序列看成是一个完全二叉树，则最后一个非终端结点是第?
2
n
个元素，由此“筛选”只需从第?
2
n
个元素开始,
至第 1 个元素。
49
38 65
97 76 13 27
49
2
n 元素 49
97
2
n -1 元素13
65
2
n -2 元素根元素13
49
49
27
第十章 内部排序第 52页堆排序 （ heap sort）
建堆排序堆排序
void HeapSort( SqList &h )
{ for( i = h.length / 2; i > 0; i-- )
HeapAdjust( h,i,h.length );
for( i = h.length; i > 1; i-- )
{ h.r[1]? h.r[i];
HeapAdjust( h,1,i-1 );
}
}
排序时，调整堆 n-1趟，
堆的大小逐趟缩小，结点数分别为 n-1,n-2,…,2,1。
堆的高度逐趟降低，分别为?Log2(n-1)?+1,?Log2(n-2)?+1,…,
Log2(2)?+1,1。
每趟比较的次数分别为 2?Log2(n-1)?,2?Log2(n-2)?,…,2,0
第十章 内部排序第 53页堆排序 （ heap sort）
算法分析：
(1) 堆排序需要时间耗费在建初始堆和调整新堆时进行的反复“筛选”上。
建堆时不超过 4n，调整建新堆时调用 HeapAdjust过程 n－ 1次，
总共进行的比较次数不超过
nnnn 2222 l o g22l o g)2(l o g)1(l o g2
堆排序最坏情况下时间复杂性为 )l o g( 2 nnO? 空间复杂性为 O ( 1 ),
(2) 堆排序不适于较小的序列排序,n很大时较有效。
(3) 堆排序不稳定。
第十章 内部排序第 54页示例,初始关键字,[ 4 9 ] [ 3 8 ] [ 6 5 ] [ 9 7 ] [ 7 6 ] [ 1 3 ] [ 2 7 ]
一趟归并,[ 3 8 4 9 ] [ 6 5 9 7 ] [ 1 3 7 6 ] [ 2 7 ]
二趟归并,[ 3 8 4 9 6 5 9 7 ] [ 1 3 2 7 7 6 ]
三趟归并：
辅助空间假设初始序列有 n 个记录，则可看成是 n 个有序的子序列，每个序列的长度为 1,然后两两归并，得到
2
n
个长度为 2 或 1 的有序子序列，
再两两归并，，如此重复，直到得到一个长度为 n 的有序序列为止，
这种排序方法称为 2 —路归并排序。
归并排序?
基本思想,将两个或两个以上的有序表组合成一个新的有序表。
具体作法：
j?i? j? j?i? i? i? j?i?
13 27 38 49 65 76 97
第十章 内部排序第 55页归并排序?
算法描述：
两组归并
void merge(RecType Sr[],RecType Tr[],int i,int m,int n )
{//Sr[i..m]和 Sr[m+1..n]分别按关键字有序，现将它们归并为一个有序序列并存放在 Tr[i..n]中
for( j = m+1,k = 1; i <= m && j <= n; k++ )
{
if(( Sr[i].key <= Sr[j].key ) { Tr[k] = Sr[i]; i++ };
else
{ Tr[k] = Sr[j]; j++ }
}
if( i≤m ) Tr[k..n] = Sr[i..m];
if( j≤n ) Tr[k..n] = Sr[ j..n];
}
比较的次数 <=m+n
赋值的次数 =m+n
第十章 内部排序第 56页归并排序?
算法描述：
归并排序的递归算法
void msort( RecType Sr[],RecType &Tr1[],int s,int t )
{//对 r[s..t]中记录进行归并排序
if( s == t ) Tr1[s] = Sr[s];
else
{ m = ( s + t ) / 2;
msort( Sr,Tr2,s,m );
msort( Sr,Tr2,m +1,t);
merge( Tr2,Tr1,s,m,t );
}
}
Void MergeSort( SqList &L)
{ msort( L.r,L.r,1,L.length );
}
第十章 内部排序第 57页
n个记录要进行多少趟归并？
要归并?Log2n? 趟。
每趟比较次数 <=n,赋值次数 =n。
归并排序的算法分析总时间复杂性为 O(nlog2n),空间复杂性为 O(n)。
归并排序是稳定的。
示例,初始关键字,[ 4 9 ] [ 3 8 ] [ 6 5 ] [ 9 7 ] [ 7 6 ] [ 1 3 ] [ 2 7 ]
一趟归并,[ 3 8 4 9 ] [ 6 5 9 7 ] [ 1 3 7 6 ] [ 2 7 ]
二趟归并,[ 3 8 4 9 6 5 9 7 ] [ 1 3 2 7 7 6 ]
三趟归并：
j?i? j? j?i? i? i? j?i?
[13 27 38 49 65 76 97]
一棵有 n个树叶的“倒”的完全二叉树，
深度为?Log2n?+1。
第十章 内部排序第 58页概述 ——多关键字的排序基数排序示例,已知扑克牌中 52张牌面的次序关系为：
2<?3<..<?A<?2<?3<..<?A
<?2<?3<..<?A<?2<?3<..<?A
每一张牌面有两个关键字：
花色（?,?,?,?）和面值（ 2,3,…,K,A），且花色的地位高于面值。现要对扑克牌进行整理。
这是一个多关键字的排序问题。
一般情况下，假设有 n 个记录的序列 },,,(
21 n
RRR? 且每个记录
i
R 中含有 d 个关键字
d
iii
KKK,,,
21
,则称序列对关键字有序递增是指：对于序列中任意两个记录 iR 和 )1( njiR j 都满足下列有序关系,
d
jjj
d
iii
KKKKKK,,,,,,
2121
其中
1
K 称为最高位关键字，
d
K 称为最低位关键字。
第十章 内部排序第 59页概述 ——多关键字的排序为实现多关键字排序,通常有两种方法：
如理牌示例中，先按花色，再按面值。
1)最高位优先（ MSD法）
先按最高位关键字排序，将序列分成若干子序列，再按次高位关键字排序分成若干更小的子序列，依次重复，最后得到有序序列。
2)最低位优先（ LSD法）
从最低位关键字开始排序，然后再对高一位排序，依次重复，
直到对最高位排序。
如理牌示例中，先按面值，再按花色。
第十章 内部排序第 60页概述 ——多关键字的排序说 明,
以整数关键字为例,若采用最高位优先,则首先按最高位分配,假设关键字取值 0~999之间,则可将 0~99的放在一个盒子中,
100~199的放在另一个盒子中,…,900~999放在最后一个盒子,
然后再将每个盒子中的关键字排序 。 这种分配方法实际上就是把一个整数看成是三位数字组合的复合关键字 。
(1)当关键字为多字段时，基数排序是一种很自然的方法，一般说来，最低位优先法要比最高位优先法简单，因为前者是从头到尾进行若干次分配与收集，执行的次数取决于构成关键字成分的多少；而后者则要分配以后处理各子集的排序问题，这通常是一个递归过程。
(2)当关键字为一简单的字段时，也可以采用分配排序的思想。
快速排序某种意义上就是可看成一种最高位优先的分配排序，
因为执行快速排序每趟都将关键字分成两组（两个盒子），然后递归处理排序问题。
第十章 内部排序第 61页基数排序其中 r称为基数 。 基数的选择和关键字的分解法,因关键字的类型而异 。 关键字为十进制整数时,最自然的取法是 r 为 10
（ 0~9）,当关键字为字符串时,可取 r =26（ A~Z） 。
基本思想,把每一个关键字看成是一个 d元组：
排序时先按 Kdi的值从小到大将记录分配到 r个盒子中，然后依次收集这些记录，再按 Kid-1的值分配到 r个盒子中，如此反复，直到对 K1i分配后收集起来的序列，便是完全排序的序列。
),,,( 21 diiii KKKK
第十章 内部排序第 62页示例 设初始关键字序列为 {278,109,063,930,589,184，
505,269,008,083}。取 r=10,d=3,c1=0,cdr=9。以 10个链队列表示 10个箱子,f [i] 和 e[i] 分别为第 i(0≤i≤9) 个队列的头指针和尾指针。
链式基数排序过程示例如下
278 109 063 930 589 184 505 269 008 083
e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
930 063 184 505 278 109
083 008 589
269
f [0] f [1] f [2] f [3] f [4] f [5] f [6] f [7] f [8] f [9]
(b)
第一趟分配之后
930 063 083 184 505 278 008 109 589 269
(c) 第一趟收集之后
(a) 初始状态第十章 内部排序第 63页链式基数排序的数据类型定义（以静态链表作存储结构）
#define MAX_NUM_OF_KEY 8 //关键字项数最大值
#define RADIX 10 //关键字基数，十进制
#define MAX_SPACE 10000
typedef struct {
KeysType Keys[MAX_NUM_OF_KEY]; //关键字
InfoType otherItems;
int next;
} SLCell;
typedef struct{
SLCell r[MAX_SPACE]; //静态链表,r[0]为头结点
int keynum; //关键字个数
int recnum; //静态链表长度
}SLList; //静态链表类型
typedef int ArrType[RADIX];
链式基数排序第十章 内部排序第 64页链式基数排序中一趟分配的算法描述
void distribute(SLCell &r,int i,ArrType &f,ArrType &e )
{//静态链表 L的 r 域中的记录按 (key[0],···,key[i-1]) 有序。本算法按第 i 位关键字 key[i] 建立子表，同一子表中记录的 key[i] 相同,f
和 e 分别指向各子表中第一个和最后一个记录。
for( j = 0; j < RADIX,j++ )
f[j]:=0; //子表初始化为空表
for( p = r[0].next; p; p = r[p].next )
{ j = ord( r[p].key[i] ); //提取记录中第 i 个关键字映射到
//[0..RADIX-1]
if( f[ j] == 0 ) f[ j] = p;
else r[e[j]].next = p;
e[j] = p; //将 p 所指结点插入第 j 个子表中
}
} 算法 10.15
链式基数排序分配工作需 O(n)
的时间第十章 内部排序第 65页链式基数排序中一趟收集的算法描述
void collect ( SLCell &r,int I,ArrType f,ArrType e )
//本算法按 key[i] 自小至大将 f[0..RADIX-1] 所指各子表链接成一个链表,e[0..RADIX-1] 为相应各子表的尾指针。
{for( j = 0; !f[j]; j = succ(j)); //找一个非空子表,succ 为求后继函数
r[0].next = f[j]; t = e[j];//r[0].next指向第一个非空子表中第一个结点
while( j < RADIX )
{ for( j = succ(j); j < RADIX-1 && !f[j]; j = succ(j));
//找下一个非空子表
if( f[j] )
{ r[t].next = f[j]; t = e[j] } //链接两个非空子表
};
r[t].next = 0 //t 指向最后一个非空子表中的最后一个结点
} 算法 10.16
链式基数排序收集需要 O(r)的时间第十章 内部排序第 66页链式基数排序的算法描述
void radixsort (SLList &L )
{//n 个记录存放在静态链表的数据域中，执行本算法进行基数排序后，链表中的记录按关键字自小至大相链。
for( i = 0; i < L.recnum; i++ )
L.r[i].next = i+1;
L.r[n].next = 0; //链表初始化
for( i = 0; i < L.keynum; i++ )
{ distribute( L.r,i,,f,e ); //第 i 趟分配
collect (L.r,i,f,e ) //第 i 趟收集
}
} 算法 10.17
链式基数排序第十章 内部排序第 67页链式基数排序链式基数排序的算法分析在链式基数排序中，没有进行关键字的比较和记录的移动，
而只是顺链扫描表和进行指针赋值，所以排序的时间主要耗费在修改指针上。
将 r 初始化成一个静态链表的时间是 O(n)。
在每一趟排序中，分配时间是 O(n)； 收集的时间是 O(rd)；
所以链式基数排序时间复杂度是 O(d*(rd+n))。显然，若 d 是常数,rd 是常数，基数排序的时间复杂度都是 O(n)，
但必须指出，当 n 较小,d 较大时，基数排序并非合适。只有当
n 较大,d 较小时，特别是记录的信息量较大时，基数排序最为有效。 在基数排序中，每一个记录中增加了一个 next 域，另外还增加 f,e 两个数组。
第十章 内部排序第 68页内部排序方法的比较和选择选取排序方法时需考虑的因素,
(1) 待排序的记录数目 n；
(2) 记录本身信息量的大小；
(3) 关键字的结构及其分布情形；
(4) 对排序稳定性的要求；
(5) 语言工具的条件；
(6) 辅助空间的大小。等等排序方法 平均时间 最坏情况 辅助存储简单排序 O ( n
2
) O ( n
2
) O ( 1)
快速排序 O ( nl ogn ) O ( n
2
) O ( l ogn )
堆 排 序 O ( nl ogn ) O ( nl ogn ) O ( 1 )
归并排序 O ( nl ogn ) O ( nl ogn ) O ( n )
基数排序 O ( d ( n + rd )) O ( d ( n + rd )) O ( rd )
下表给出各种排序方法的主要性能第十章 内部排序第 69页
(2) 若 n 较大，则应采用时间复杂度为 O(nlogn) 的排序方法，如快速排序、堆排序或归并排序等。快速排序是目前基于比较的内部排序中被认为是最好的方法。当待排序的关键字是随机分布时，快速排序的平均时间最短，但堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
内部排序方法的比较和选择?
内部排序方法的比较和选择
(1) 若 n 较小，则可选用直接插入排序或直接选择排序。
(3) 基数排序的时间复杂度也可写成 O(d·n)，它最适合于 n 值很大而关键字较小的序列。
(4) 从方法的稳定性来比较，基数排序是稳定的内部排序方法，所有时间复杂度为 O(n2) 的简单排序法也是稳定的；然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。
由于大多数情况下排序是按记录的主关健字进行的，故所选用的排序方法是否稳定无关紧要。
第十章 内部排序第 70页第十章 内部排序 小结基本内容
五类内部排序方法（插入排序、交换排序、选择排序、归并排序、基数排序）的基本思想、排序过程和实现算法
各类排序算法的时间复杂度分析
各种排序方法的比较和选择学习要点
深刻理解各种内部排序方法的基本思想及其特点
熟悉各种排序方法的排序过程
理解各种排序方法的算法实现及时间复杂度分析第十章 内部排序第 71页复 习一,全面复习二,以教材为主基本概念基本算法基本应用
ADT
类 C 描述一般的时空效率分析三,以课堂讲授内容为准四,课外作业、课堂小练习、上机作业第十章 内部排序第 72页
