先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除 多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记录,其关键字分别是:
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次为:
5,3,1
缩小增量法
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止
初始:d=5
49 38 65 97 76 13 27 49 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49*
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟结果
13 27 49* 55 04 49 38 65 97 76
d=3
13 27 49* 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49* 49 97
|------------|------------|
二趟结果
13 04 49* 38 27 49 55 65 97 76
d=1
13 04 49* 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟结果
04 13 27 38 49 49 55 65 76 97
--------------------------------------------------------------------------------------------
Shell排序
Shell排序的算法实现:
1. 不设监视哨的算法描述
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的插入位置
R[j+d]=R[j]; //后移记录
j=j-d; //查找前一记录
}while(j>0&&R[0].key<R[j].key);
R[j+d]=R[0]; //插入R到正确的位置上
} //endif
不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法, 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是 最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快, 再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
时间性能
1.增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征:
① 最后一个增量必须为1;
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验,给出了目前较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。
2.Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
因此,希尔排序在效率上较直接插人排序有较大的改进。
打开IDE
创建一个工程
声名如下
#include<iostream>#include<iomanip>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define MAXI 11
typedef int KeyType;
typedef int ElemType;
struct rec {
KeyType key;ElemType data;};
typedef rec sqlist[MAXI];
void shellsort(sqlist b,int n)
{int i,j,gap,k;rec x;
gap=n/2;
while(gap>0)
{for(i=gap+1;i<n;i++)
{j=i-gap;
while(j>0)
if(b[j].key>b[j+gap].key)
{x=b[j];b[j]=b[j+gap];
b[j+gap]=x;j=j-gap;}
else j=0;
for(k=1;k<n;k++)
cout<<setw(4)<<b[k].key;
cout<<endl;}
gap=gap/2;}
}
调用如下
void main(){cout<<"运行结果:\n";sqlist a;int i,n=MAXI;srand(time(0));for(i=1;i<n;i++){a[i].key=rand()%80;a[i].data=rand()%100;}cout<<"排序前数组:\n";for(i=1;i<n;i++)cout<<setw(4)<<a[i].key;cout<<endl;cout<<"数组排序过程演示:\n";shellsort(a,n);cout<<"排序后数组:\n";for(i=1;i<n;i++)cout<<setw(4)<<a[i].key;cout<<endl;cin.get();}
运行如下
代码下载