一 排序的基本概念
所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来. 其确切定义如下:
输入: n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn.
输出: Ril,Ri2,…,Rin,使得Ki1 ≤ Ki2 ≤ … ≤ Kin.(或Ki1 ≥ Ki2 ≥ … ≥ Kin.)
二 排序的分类
1. 按是否涉及数据的内、外存交换分为
内部排序: 内部排序(简称内排序),是带排序纪录存放在计算机内存中进行的排序过程. 细分又可为插入排序、选择排序、交换排序、归并排序和基数排序.
外部排序: 外部排序(简称外排序),是带排序纪录的数量很大,以至于内存一次不能容纳全部纪录,在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序的排序方法.
2. 按策略划分内部排序方法
可以分为五类: 插入排序、选择排序、交换排序、归并排序和基数排序.
三 排序算法的基本操作
1. 比较两个关键字的大小
2. 改变指向记录的指针或移动记录本身
注意: 第2种基本操作的实现依赖于待排序记录的存储方式.
四 排序算法的性能评价
1. 评价排序算法好坏的标准
(1)执行时间和所需的辅助空间
(2)算法本身的复杂程度
2. 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-Place Sort). 非就地排序一般要求的辅助空间为O(n).
3. 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动. 有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态.
1 插入排序
1.1 直接插入排序
定义: 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法. 它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中,使之仍保持有序,从而得到一个新的长度为m＋1的有序表.
算法思路: 设有一组关键字{K1,K2,…,Kn},排序开始就认为K1是一个有序序列,让K2 插入上述表长为1的有序序列,使之成为一个表长为2的有序序列,然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为 n-1的有序序列,得一个表长为n的有序序列.
算法时间复杂度: 此算法外循环n-1次,在一般情况下内循环平均比较次数的数量级为Ｏ(n),所以算法总时间复杂度为Ｏ(n^2).
直接插入排序的稳定性: 直接插入排序是稳定.的排序方法
具体算法:
/* 比较数据函数模板 */
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1, const Type *Data_2) ;
// InsertSort
template<class Type>
void InsertSort (TypeArray[], int n, PFunCustomComparepfCompare)
{
int i , j ;
for (i = 2 ; i <= n ; i ++) // 进行n-1趟插入
{
Array[0] = Array[i] ; // Array[0]为监视哨,也可作下边循环结束标志
j = i - 1 ;
while ( pfCompare(Array[j], Array[0]) )
{
Array[j+1] = Array[j] ;
j -- ;
}
Array[j+1] = Array[0] ; // 将r[0]即原r[i]记录内容,插到r[j]后一位置
}
}
// 或者:不需要监视哨
template<class Type>
void __stdcall InsertSort(TypeArray[], int Num, PFunCustomComparepfCompare)
{
for (int i = 1 ; i < Num ; i ++)
{
Typetemp = Array[i] ;
int j ;
for (j = i-1 ; j >= 0 && pfCompare(temp, Array[j]) ; j --)
Array[j+1] = Array[j] ;
Array[j+1] = temp ;
}
}
例1 设有一组关键字序列{55,22,44,11,33},这里n = 5,即有5个记录. 请将其按由小到大的顺序排序. 排序过程如下所示:
第一趟: [55] 22 44 11 33
第二趟: [22 55] 44 11 33
第三趟: [22 44 55] 11 33
第四趟: [11 22 44 55] 33
第五趟: [11 22 33 44 55]
1.2 折半插入排序
定义: 当直接插入排序进行到某一趟时,对于r[i].key来讲,前边i-1个记录已经按关键字有序.此时不用直接插入排序的方法,而改为折半查找,找出r[i].key应插的位置,然后插入. 这种方法就是折半插入排序(Binary Insertion Sort).
具体算法:
// BinarySort
template<class T>
void BinarySort(Ta[], int n)
{
int i , j , l , h , mid ;
for (i = 2 ; i <= n ; i ++)
{
a[0] = a[i] ;
l = 1 ; h = i-1 ; // 认为在a[1]和a[i-1]之间已经有序
while (l <= h) // 对有序表进行折半查找
{
mid = (l+h) / 2 ;
if(a[0].key < a[mid].key)
h = mid-1 ;
else
l = mid+1 ;
}
// 结果在mid位置
for(j = i-1 ; j >= mid ; j --)
a[j+1] = a[j] ;
a[mid] = a[0] ;
}
}
算法时间复杂度: 折半插入排序,关键字的比较次数由于采用了折半查找而减少,数量级为O (n*log(n)),但是元素移动次数仍为Ｏ(n^2). 故折半插入排序时间复杂度仍为Ｏ(n^2).
折半插入排序的稳定性: 折半插入排序方法是稳定.的
1.3 2路插入排序
1.4 表插入排序
1.5 希尔排序
定义: 希尔排序(Shell Sort)是D.L.希尔(D.L.Shell)提出的“缩小增量”的排序方法. 它的作法不是每次一个元素挨一个元素的比较. 而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置,然后增量缩小,最后增量为1,这样记录移动次数大大减少,提高了排序效率. 希尔排序对增量序列的选择没有严格规定.
算法思路:
① 先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成一组,然后在各组内进行插入排序 ;
② 然后取 d2 (d2<d1) ;
③ 重复上述分组和排序操作,直到取di=1 (i>=1),即所有记录成为一个组为止. 一般选d1约为n/2,d2为d1/2,d3为d2/2,…,di=1.
具体算法:
/* 比较数据函数模板 */
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1, const Type *Data_2) ;
template <class Type>
void __stdcall ShellSort(TypeArray[], int Num, PFunCusomCompare pfCompare)
{
d = Num ;
do
{
d = d/2 ; // 一般增量设置为数组元素个数,不断除以2以取小
for (int i = d+1 ; i <= Num ; ++ i)
{
if (pfCompare(Array[i], Array[i-d]))
{
Typetemp = Array[i] ;
for (int j = i-d ; j > 0 && fpCompare(temp, Array[j]) ; j = j-d)
Array[j-d] = Array[j] ;
Array[j+d] = temp ;
}
}
}while (d > 1) ;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Example two :
void ShellPass(SeqList R, int d)
{
//希尔排序中的一趟排序,d为当前增量
for(i = d+1 ; i <= n ; i ++) // 将R[d+1..n]分别插入各组当前的有序区
if(R[i].key < R[i-d].key)
{
R[0] = R[i] ;
j = i-d ; //R[0]只是暂存单元,不是哨兵
do
{
//查找R[i]的插入位置
R[j+d] = R[j] ; //后移记录
j = j-d ; //查找前一记录
}while (j > 0 && R[0].key < R[j].key) ;
R[j+d] = R[0] ; //插入R[i]到正确的位置上
} // endif
} // ShellPass
void ShellSort(SeqList R)
{
int increment = n ; //增量初值,不妨设n>0
do
{
increment = increment/3 + 1 ; //求下一增量
ShellPass(R, increment) ; //一趟增量为increment的Shell插入排序
}while (increment > 1) ;
} // ShellSort
注意: 当增量d=1时,ShellPass和InsertSort基本一致,只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0",以防下标越界.
算法分析:
① 增量序列的选择
Shell排序的执行时间依赖于增量序列. 好的增量序列的共同特征: 最后一个增量必须为1 ; 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况. 有人通过大量的实验,给出了目前比较好的结果: 当n较大时,比较和移动的次数在n1.25至1.6n1.25之间.
② Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因: 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少 ; 当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大 ; 在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快. 因此,希尔排序在效率上较直接插入排序有较大的改进.
③ 稳定性
希尔排序是不稳定.的
2 选择排序
选择排序(Selection Sort)的基本思想是: 每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕.
2.1 简单选择排序
定义: 简单选择排序(Simple Selection Sort)也是直接选择排序. 此方法在一些高级语言课程中做过介绍,是一种较为容易理解的方法.
算法思想: 对于一组关键字{K1,K2,…,Kn},首先从K1,K2,…,Kn中选择最小值,假如它是Kz,则将Kz与K1对换,然后从K2,K3,…,Kn中选择最小值Kz,再将Kz与K2对换. 如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1、Kn中选择最小值Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 即: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止.
具体算法:
/* 比较数据函数模板 */
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1,const Type *Data_2) ;
/* 交换数据函数模板 */
template<class Type>
typedef void __stdcall (*PFunCusomSwap)(const Type *Data_1,const Type *Data_2) ;
template<class Type>
void __stdcall SelectSort(TypeArray[], int Num, PFunCusomCompare pfCompare, PFunCusomSwap pfSwap)
{
for (int i = 0 ; i < Num-1 ; ++ i)
{
//从i~n-1中选择要选的数据
int min = i ;
for (int j = i+1 ; j < Num ; ++ j)
if (pfCompare (Array[j], Array[min]))
min = j ;
if(min != i)
pfSwap(Array[j],Array[min]) ;
}
}
算法分析:
1. 关键字比较次数
无论文件初始状态如何,在第i趟排序选出最小关键字的记录,需做n-i次比较,因此总的比较次数为: n(n-1)/2 = O(n2).
2. 记录的移动次数
当初始文件为正序时,移动次数为0 ;
文件初态反序时,每趟排序均要执行交换操作,中的移动次数取最大值(n-1) ;
直接选择排序的平均时间复杂度为O(n2) .
3. 直接选择排序是一个就地排序
4. 稳定性分析
直接选择排序是不稳定的.
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).
基数排序是稳定的.
5.3 鸽巢排序
6 并行排序