希尔排序【Shellsort】

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。——维基百科

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

– 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

– 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法实现

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

推荐步长： 3*n+1

算法分析

1．增量序列的选择

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征：

– 最后一个增量必须为1；

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

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

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

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

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

3．稳定性

希尔排序是不稳定的。

排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

public class Shell
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h +1;
        while(h >= 1)
        {
            for(int i=h; i<N; i++)
            {
                for(int j=i; j>=h && less(a[j],a[j-h]); j-=h)
                    exch(a,j,j-h);
            }
            h = h/3;
        }
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}

• 上一篇
• 下一篇

版权属于: 尾尾部落

原文地址: https://cloud.tencent.com/developer/article/1327578

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')0||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];