加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

希尔排序(Shell Sort)

(2013-08-27 20:22:50)
标签:

希尔排序

排序

算法

it

分类: 数据结构

希尔排序(Shell Sort)插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2

该方法实质上是一种分组插入方法。

希尔排序的基本思想是:将需要排序的序列划分成为若干个较小的子序列,对子序列进行插入排序,通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率,缩小增量.

希尔排序(Shell <wbr>Sort)

希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序

排序过程:先取一个正整数d1数组元素放一组,组内进行直接插入排序;然后取d2

先假如:数组的长度为10,数组元素为:25,19,6,58,34,10,7,98,160,0

        整个希尔排序的算法过程如下如所示:

希尔排序(Shell <wbr>Sort)

  上图是原始数据和第一次选择的增量 d = 5。本次排序的结果如下图:

希尔排序(Shell <wbr>Sort)

 

上图是第一次排序的结果,本次选择增量为 d=2。 本次排序的结果如下图:

希尔排序(Shell <wbr>Sort)

当d=1 是进行最后一次排序,本次排序相当于冒泡排序的某一次循环。最终结果如下:

希尔排序(Shell <wbr>Sort)
优劣

不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法, 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度与增量序列的选取有关,例如希尔增量时间复杂度为O(n^2),而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4)),但是现今仍然没有人能找出希尔排序的精确下界。希尔排序没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O(N^2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

时间性能

1.增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征:

① 最后一个增量必须为1;

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验,给出了较好的结果:当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。

2.Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因:

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

③在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。

因此,希尔排序在效率上较直接插入排序有较大的改进。

稳定性

排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法是稳定的,反之就是不稳定的。通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。再简单形式化一下,如果Ai = Aj, Ai原来在Aj位置前,排序后Ai还是要在Aj位置前。

希尔分析

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

 具体的C++算法分析

#include
using namespace std;
void Display(int array[],int length);
void ShellSort(int array[],int length);
int main(int argc, char* argv[])
{
         int arr[10] = {25,19,6,58,34,10,7,98,160,0};
         Display(arr,10);
         ShellSort(arr,10);
         Display(arr,10);
         system("pause");

//system("pause")就是从程序里调用“pause”命令;而“pause”这个系统命令     

//的功能很简单,就是在命令行上输出一行类似于“Press   any key                     

 //to exit”的字,等待用户按一个键,然后返回。


         return 0;
}
//输出数组
void Display(int array[],int length)
{
         for(int i =0;i<length;i++)
         {
                   cout<<array[i]<<", ";
         }
         cout<<endl;
}
//希尔排序算法的实现  
void ShellSort(int array[],int length)
{
         int d = length/2;   //设置希尔排序的增量
         int i ;
         int j;
         int temp;
         while(d>=1)
         {
                   for(i=d;i<length;i++)
                   {
                            temp=array[i];
                            j=i-d;
                            while(j>=0 && array[j]>temp)
                            {
                                     array[j+d]=array[j];
                                     j=j-d;
                            }
                            array[j+d] = temp;
                   }
                   Display(array,10);
                   d= d/2;    //缩小增量
         }
}

运行结果

希尔排序(Shell <wbr>Sort)

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有