2.2 堆排序
定义: 树形选择排序(锦标赛排序),1964年威洛姆斯(J.Willioms)提出了进一步改正的排序方法,即堆排序(Heap Sort).
堆是n个元素的有限序列{K1,K2,…,Kn},它当且仅当满足如下关系:
这是一个上小、底大的堆. 若是一个上大、底小的堆,只需把“<=”改为“>=”即可. 堆是一种数据元素之间的逻辑关系,常用向量做存储结构. 对于满二叉树,当对它的结点由上而下,自左至右编号之后,编号为i的结点是编号为2i和2i+1结点的双亲. 反过来讲,结点2i是结点i的左孩子,结点2i+1是结点i的右孩子. 图9.7表示完全二叉树和它在向量中的存储状态. 结点编号对应向量中的下标号. 用堆的概念分析向量中的数据,它显然满足(上小、底大)堆的关系. 不难看出满足堆的逻辑关系的一组数据,可画成二叉树的形状,并且它是一棵完全二叉树树形. 因此,也可借助完全二叉树来描述堆的概念. 若完全二叉树中任一非叶子结点的值小于等于(或大于等于)其左、右孩子结点的值,则从根结点开始按结点编号排列所得的结点序列就是一个小根(大根)堆. 在图9.8中(a)、(c)是堆, (b)、(d)不是堆.
堆排序的算法思想: 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单.
（1）用大根堆排序的基本思想
①. 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
②. 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys ≤ R[n].key
③. 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆. 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆.
④. ……
⑤. 直到无序区只有一个元素为止.
（2）大根堆排序算法的基本操作:
①. 初始化操作: 将R[1..n]构造为初始堆 ;
②. 每一趟排序的基本操作: 将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆).
注意:
① 只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序.
② 用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的. 堆排序和直接选择排序相反: 在任何时刻,堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止.
具体算法:
建堆(BuildHeap)和堆化(Heapify)函数的实现:
因为构造初始堆必须使用到调整堆的操作,先讨论Heapify的实现.
以R[1]为根的堆,在R[1]与R[i]交换后,新的无序区R[1..i-1]中只有R[1]的值发生了变化,故除R[1]可能违反堆性质外,其余任何结点为根的子树均是堆. 因此,当被调整区间是R[low..high]时,只须调整以R[low]为根的树即可. "筛选法"调整堆R[low]的左、右子树(若存在)均已是堆,这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点. 若R[low].key不小于这两个孩子结点的关键字,则R[low]未违反堆性质,以R[low]为根的树已是堆,无须调整; 否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换,即R[low]与R[large](R[large].key=max(R[2low].key,R[2low+1].key))交换. 交换后又可能使结点R[large]违反堆性质,同样由于该结点的两棵子树(若存在)仍然是堆,故可重复上述的调整过程,对以R[large]为根的树进行调整. 此过程直至当前被调整的结点已满足堆性质,或者该结点已是叶子为止. 上述过程就象过筛子一样,把较小的关键字逐层筛下去,而将较大的关键字逐层选上来. 因此,有人将此方法称为"筛选法".
BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆,就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆. 显然只有一个结点的树是堆,而在完全二叉树中,所有序号大于n/2的结点都是叶子,因此以这些结点为根的子树均已是堆. 这样,我们只需依次将以序号为n/2,…,1的结点作为根的子树都调整为堆即可.
//--------------------------------------------------------------------------------------
template <class type> static void HeapIfy (type *arry, int size, int index) ;
template <class type> inline static void BuildHeap (type *arry, int size) ;
template <class type> static void HeapSort (type *arry, int size) ;
//--------------------------------------------------------------------------------------
template <class type>
static void HeapSort (type *arry, int size)
{
if (size <= 1) return ;
BuildHeap (arry, size) ;
int count = size ;
while (count >= 2)
{
typetemp = arry[count-1] ;
arry[count-1] = arry[0] ;
arry[0] = temp ;
count -- ;
BuildHeap (arry, count) ;
}
}
//--------------------------------------------------------------------------------------
template <class type>
inline static void BuildHeap (type *arry, int size)
{
#if _DEBUG
assert (arry && size > 0) ;
#endif
int i = (size-1)/2 ;
for ( ; i >= 0 ; i --)
HeapIfy (arry, size, i) ;
}
//--------------------------------------------------------------------------------------
static void HeapIfy (type *arry, int size, int index)
{
// 平衡堆,参数为数组,数组长度,加入的元素下标
#if _DEBUG
assert (arry && size > 0 && index >= 0 && index < size) ;
#endif
int m = index ; // 本身索引
int l ;
int r ;
do
{
l = m*2 + 1 ; // 左儿子索引
r = l + 1 ; // 右儿子索引
if (l >= size) //无儿子
return ;
else if (r >= size)
{
// 无右儿子
if (arry[m] >= arry[l])
return ;
else
{
typetemp = arry[m] ;
arry[m] = arry[l] ;
arry[l] = temp ;
return ;
}
if (arry[l] >= arry[r])
{
if (arry[m] >= arry[l])
return ;
typetemp = arry[m] ;
arry[m] = arry[l] ;
arry[l] = temp ;
m = l ;
continue ;
}
}
else
{
if (arry[m] >= arry[r])
return ;
typetemp = arry[m] ;
arry[m] = arry[r] ;
arry[r] = temp ;
m = r ;
continue ;
}
}while (true) ;
}
算法时间复杂度:
堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的树高度log2n相关. 而 heapsort中对heap的调用数量级为n,所以堆排序的整个时间复杂度为O(nlog2n). 并且堆排序是不稳定的.
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的.
堆排序的最坏时间复杂度为O(nlog(n)),堆排序的平均性能较接近于最坏性能.
由于建初始堆所需的比较次数较多,所以堆排序不适于记录数较少的文件.
堆排序是就地排序,辅助空间为O(1).
堆排序是不稳定的.
3 交换排序
交换排序主要是根据记录的关键字的大小,将记录交换来进行排序的. 交换排序的特点是: 将关键字值较大的记录向序列的后部移动,关键字较小的记录向前移动. 这里介绍两种交换排序方法,它们是冒泡排序和快速排序.
3.1 冒泡排序
定义: 将被排序的记录数组R[1...n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡. 根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R: 凡扫描到违反本原则的轻气泡,就使其向上"飘浮". 如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止.
算法思路:
(1) 让j取n至2,将r[j].key与r[j-1].key比较,如果r[j].key < r[j-1].key,则把记录r[j]与r[j-1]交换位置,否则不进行交换. 最后是r[2].key与r[1].key对比,关键字较小的记录就换到r[1]的位置上,到此第一趟结束. 最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边.
(2) 让j取n至3,重复上述的比较对换操作,最终r[2]之中存放的是剩余n-1个记录(r[1]除外)中关键字最小的记录.
(3) 让j取n至i+1,经过一系列对联对比交换之后,r[i]之中是剩余若干记录中关键字最小的记录.
(4) 让j取n至n-1,将r[n].key与r[n-1].key对比,把关键字较小的记录交换到r[n-1]之中.
例 设有一组关键字序列{55,22,44,11,33},这里n=5,即有5个记录. 请将其按由小到大的顺序排序.
具体算法:
template<class Type>
BubbleSort(TypeArray[], int n)
{
int t = 1, tag, j ;
Tx ;
do
{
tag = 0 ;
for(j = n ; j >= i ; j --)
if(r[j].key < r[j-1].key)
{
x = r[j] ;
r[j] = r[j-1] ;
r[j-1] = x ;
tag = 1 ;
}
i ++ ;
}while (tag == 1 && i <= n) ;
} // BubbleSort
算法时间复杂度: 该算法的时间复杂度为O(n2). 但是,当原始关键字序列已有序时,只进行一趟比较就结束,此时时间复杂度为O(n).
3.2 鸡尾酒排序(冒泡排序变形)
3.3 快速排序
定义: 快速排序由霍尔(Hoare)提出,它是一种对冒泡排序的改正. 由于其排序速度快,故称快速排序(Quick Sort). 快速排序方法的实质是将一组关键字[K1,K2,…,Kn]进行分区交换排序.
算法思路:
① 以第一个关键字K1为控制字,将[K1,K2,…,Kn]分成两个子区,使左区所有关键字小于等于K1,右区所有关键字大于等于K1,最后控制字居两个子区中间的适当位置. 在子区内数据尚处于无序状态.
② 将右区首、尾指针(记录的下标号)保存入栈,对左区进行与第①步相类似的处理,又得到它的左子区和右子区,控制字居中.
③ 后退栈对一个个右子区进行相类似的处理,直到栈空.
由以上三步可以看出: 快速排序算法总框架是进行多趟的分区处理,而对某一特定子区,则应把它看成又是一个待排序的文件,控制字总是取子区中第一个记录的关键字. 现在设计一个函数hoare,它仅对某一待排序文件进行左、右子区的划分,使控制字居中,再设计一个主体框架函数quicksort,在这里多次调用hoare函数以实现对整个文件的排序.
快速排序算法分析:
快速排序的非递归算法引用了辅助栈,它的深度为log(n). 假设每一次分区处理所得的两个子区长度相近,那么可入栈的子区长度分别为: n/(2*1),n/(2*2),n/(2*3),n/(2*4),…,n/(2*k).又因为n/2k=1,所以 k= log2(n). 分母中2的指数恰好反映出需要入栈的子区个数,它就是 log2n,也即栈的深度. 在最坏情况下,比如原文件关键字已经有序,每次分区处理仅能得到一个子区. 可入的子区个数接近n,此时栈的最大深度为n.
快速排序主体算法时间运算量约O(log2n),划分子区函数运算量约O(n),所以总的时间复杂度为O(nlog2n),它显然优于冒泡排序O(n2). 可是算法的优势并不是绝对的. 试分析,当原文件关键字有序时,快速排序时间复杂度是O(n2),这种情况下快速排序不快. 而这种情况的冒泡排序是O(n),反而很快. 在原文件记录关键字无序时的多种排序方法中,快速排序被认为是最好的一种排序方法.
例 试用[6,7,5(1),2,5(2),8]进行快速排序.
排序过程简述如下
6 7 5(1) 2 5(2) 8 初始状态
[5(2) 7 5(1)] 6 [7 8]
[2] 5(2) [5(1)] 6 7 [8]
[2 5(2) 5(1) 6 7 8] 最后状态
从这个例子可以分析出快速排序法的稳定性问题,其中51和52表示两个关键字的值相同,都是5. 5(1)表示排序之前它位于5(2)的前面. 从结果中可以看出原先位于5(1)之后的5(2)在排序之后移到了5(1)的前面,所以说快速排序是不稳定的.
具体算法:
template <class Type>
void __stdcall QuickSort(TypeArray[], int Num, PFunCusomCompare pfCompare, PFunCusomSwap pfSwap)
{
int left = 0 ;
int right = Num-1 ;
do
{
int i = left , j = right ;
TypeMidData = Array[(left+right)/2] ;
do
{
while (fpCompare (MidData, Array[i]) && i < right)
{
// 从左扫描大于中值的数
++ i ;
}
while (fpCompare (Array[j], MidData) && j > left)
{
// 从右扫描大于中值的数
-- j ;
}
if (i <= j)
{
pfSwap(Array[i], Array[j]) ; // 交换数据
++ i ;
-- j ;
}
}while (i <= j) ;// 如果两边扫描的下标交错,就停止(完成一次)
if (left < j)
{
// 当左边部分有值(left<j),递归左半边
left = left ;
}
if (right > i)
{
//当右边部分有值(right>i),递归右半边
left = i ;
right = right ;
}
}while (left <= right) ;
}
4 归并排序
定义: 归并排序(Merge Sort)是一类与插入排序、交换排序、选择排序不同的另一种排序方法.归并的含义是将两个或两个以上的有序表合并成一个新的有序表. 归并排序有多路归并排序、两路归并排序,可用于内排序,也可以用于外排序. 这里仅对内排序的两路归并方法进行讨论.
两路归并排序算法思路:
①. 把n个记录看成n个长度为l的有序子表 ;
②. 进行两两归并使记录关键字有序,得到n/2个长度为2的有序子表 ;
③. 重复第②步直到所有记录归并成一个长度为n的有序表为止 ;
算法实现:
此算法的实现不像图示那样简单,现分三步来讨论. 首先从宏观上分析,首先让子表表长L=1进行处理,不断地使L=2*L,进行子表处理,直到L>=n为止,把这一过程写成一个主体框架函数mergesort. 然后对于某确定的子表表长L,将n个记录分成若干组子表,两两归并,这里显然要循环若干次,把这一步写成一个函数mergepass,可由mergesort调用. 最后再看每一组(一对)子表的归并,其原理是相同的,只是子表表长不同,换句话说,是子表的首记录号与尾记录号不同,把这个归并操作作为核心算法写成函数merge,由mergepass来调用.
具体算法:
// 归并操作
template <class type>
static void Merge (typearray[], int p, int q, int r)
{
int i , k ;
int begin1 , end1 , begin2 , end2 ;
int* temp = (int*)malloc((r-p)*sizeof(int)) ;
begin1 = p ;
end1 = q ;
begin2 = q+1 ;
end2 = r ;
k = 0 ;
while (begin1 <= end1 && begin2 <= end2)
{
if (array[begin1] < array[begin2])
{
temp[k] = array[begin1] ;
begin1 ++ ;
}
else
{
temp[k] = array[begin2] ;
begin2 ++ ;
}
k ++ ;
}
while (begin1 < end1)
{
temp[k++] = array[begin1++] ;
}
while (begin2 < end2)
{
temp[k++] = array[begin2++] ;
}
for (i = 0 ; i < (r-p) ; i ++)
{
array[p+i] = temp ;
}
free(temp) ;
}
//--------------------------------------------------------------------------------------
template <class type>
void MergeSort(typearray[], unsigned int first, unsigned int last)
{
int mid = 0 ;
if (first < last)
{
mid = (first+last)/2 ;
MergeSort (array, first, mid) ;
MergeSort (array, mid+1, last) ;
Merge (array, first, mid, last) ;
}
}
算法分析:
1. 稳定性,归并排序是一种稳定的排序.
2. 存储结构要求,可用顺序存储结构,也易于在链表上实现.
3. 时间复杂度,对长度为n的文件,需进行log(n)趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog(n)).
4. 空间复杂度,需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序.
注意: 若用单链表做存储结构,很容易给出就地的归并排序.
5 分配排序
分配排序的基本思想: 排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序. 它们的时间复杂度可达到线性阶: O(n).
5.1桶排序
这里先介绍箱排序.
箱排序的基本思想:
箱排序也称桶排序(Bucket Sort),其基本思想是: 设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集).
例要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序,需设置13个"箱子",排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌.
箱排序中,箱子的个数取决于关键字的取值范围
若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子. 因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子.
箱子的类型应设计成链表为宜
一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜.
为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行.
实现方法一
每个箱子设为一个链队列. 当一记录装入某箱子时,应做入队操作将其插入该箱子尾部,而收集过程则是对箱子做出队操作,依次将出队的记录放到输出序列中.
实现方法二
若输入的待排序记录是以链表形式给出时,出队操作可简化为是将整个箱子链表链接到输出链表的尾部. 这只需要修改输出链表的尾结点中的指针域,令其指向箱子链表的头,然后修改输出链表的尾指针,令其指向箱子链表的尾即可.
算法简析
分配过程的时间是O(n),收集过程的时间为O(m),(采用链表来存储输入的待排序记录)或O(m+n). 因此,箱排序的时间为O(m+n). 若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n).
注意: 箱排序实用价值不大,仅适用于作为基数排序(下节介绍)的一个中间步骤.
箱排序的变种. 为了区别于上述的箱排序,姑且称它为桶排序(实际上箱排序和桶排序是同义词).
桶排序基本思想
桶排序的思想是把[0,1)划分为n个大小相同的子区间,每一子区间是一个桶. 然后将n个记录分配到各个桶中. 因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多个记录落入同一个桶中. 由于同一桶中的记录其关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序,然后依次将各非空桶中的记录连接(收集)起来即可.
注意: 这种排序思想基于以下假设: 假设输入的n个关键字序列是随机分布在区间[0,1)之上.若关键字序列的取值范围不是该区间,只要其取值均非负,我们总能将所有关键字除以某一合适的数,将关键字映射到该区间上. 但要保证映射后的关键字是均匀分布在[0,1)上的.
桶排序算法
伪代码算法为:
void BucketSon(R)
{
//对R[0..n-1]做桶排序,其中0 ≤ R[i].key < 1 (0 ≤ i < n)
for(i = 0 ; i < n ; i ++) // 分配过程
将R[i]插入到桶B[「n(R[i].key)」]中 ; // 可插入表头上
for(i = 0 ; i < n ; i ++) // 排序过程
当B[i]非空时用插人排序将B[i]中的记录排序 ;
for(i = 0 ; i < n ; i ++) // 收集过程
若B[i]非空,则将B[i]中的记录依次输出到R中 ;
}
注意: 实现时需设置一个指针向量B[0..n-1]来表示n个桶. 但因为任一记录R[i]的关键字满足: 0≤R[i].key<1(0≤i≤n-1),所以必须将R[i].key映射到B的下标区间[0,n-1)上才能使R[i]装入某个桶中,这可通过「n*(R[i].key)」来实现.
桶排序算法分析
桶排序的平均时间复杂度是线性的,即O(n). 但最坏情况仍有可能是O(n2).
箱排序只适用于关键字取值范围较小的情况,否则所需箱子的数目m太多导致浪费存储空间和计算时间.
例n=10,被排序的记录关键字ki取值范围是0到99之间的整数(36,5,16,98,95,47,32,36,48)时,要用100个箱子来做一趟箱排序. (即若m=n2时,箱排序的时间O(m+n)=O(n2)).
5.2 基数排序
基数排序(Radix Sort)是对箱排序的改进和推广.
单关键字和多关键字
文件中任一记录R[i]的关键字均由d个分量构成.
若这d个分量中每个分量都是一个独立的关键字,则文件是多关键字的(如扑克牌有两个关键字: 点数和花色),否则文件是单关键字的, (0≤j<d)只不过是关键字中其中的一位(如字符串、十进制整数等).
多关键字中的每个关键字的取值范围一般不同. 如扑克牌的花色取值只有4种,而点数则有13种. 单关键字中的每位一般取值范围相同.
基数
设单关键字的每个分量的取值范围均是: C0≤kj≤Crd-1(0≤j<d), 可能的取值个数rd称为基数.
基数的选择和关键字的分解因关键字的类型而异:
(1) 若关键字是十进制整数,则按个、十等位进行分解,基数rd=10,C0=0,C9=9,d为最长整数的位数;
(2) 若关键字是小写的英文字符串,则rd=26,Co='a',C25='z',d为字符串的最大长度.
基数排序的基本思想
基数排序的基本思想是: 从低位到高位依次对Kj(j=d-1,d-2,…,0)进行箱排序. 在d趟箱排序中,所需的箱子数就是基数rd,这就是"基数排序"名称的由来.
算法分析
若排序文件不是以数组R形式给出,而是以单链表形式给出(此时称为链式的基数排序),则可通过修改出队和人队函数使表示箱子的链队列无须分配结点空间,而使用原链表的结点空间. 入队出队操作亦无需移动记录而仅需修改指针. 虽然这样一来节省了一定的时间和空间,但算法要复杂得多,且时空复杂度就其数量级而言并未得到改观.
基数排序的时间是线性的(即O(n)).
基数排序所需的辅助存储空间为O(n+rd).
基数排序是稳定的.
