VC++2012编程演练数据结构《33》希尔排序

时间:2021-12-22 00:12:54
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
先取一个小于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

VC++2012编程演练数据结构《33》希尔排序

创建一个工程
VC++2012编程演练数据结构《33》希尔排序



声名如下


#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();}





运行如下

VC++2012编程演练数据结构《33》希尔排序


代码下载

http://download.csdn.net/detail/yincheng01/4790041