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. 稳定性分析
直接选择排序是不稳定的.
