希尔排序概述

希尔排序因计算机科学家Donald1.Shell而得名，他在1959年发现了希尔排序算法。希尔排序基于插入排序，但是增加了一个新的特性，大大地提高了插入排序的执行效率。

依靠这个特别的实现机制，希尔排序对于多达几千个数据项的，中等大小规模的数组序表现良好。希尔排序不像快速排序和其他时间复杂度为O(N*IogN)的排序算法那么快，因此对非常大的文件排序，它不是最优选择。但是，希尔排序比选择排序和插入排序这种时间复杂度为O(n^2)的排序算法还是要快得多，并且它非常容易实现:希尔排序算法的代码既短又简单。

它在最坏情况下的执行效率和在平均情况下的执行效率相比没有差很多。一些专家提倡差不多任何排序工作在开始时都可以使用希尔排序算法,若在实际中证明它不够快，再改换成诸如快速排序这样更高级的排序算法。

希尔排序过程图示

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。

如图示例：

（1）初始增量第一趟 gap = length/2 = 4

希尔排序java代码

//--------------------------------------------------------------
class ArraySh {
    private long[] theArray; // ref to array theArray
    private int nElems; // number of data items

    //--------------------------------------------------------------
    public ArraySh(int max) // constructor
    {
        theArray = new long[max]; // create the array
        nElems = 0; // no items yet
    }

    //--------------------------------------------------------------
    public void insert(long value) // put element into array
    {
        theArray[nElems] = value; // insert it
        nElems++; // increment size
    }

    //--------------------------------------------------------------
    public void display() // displays array contents
    {
        System.out.print("A=");
        for (int j = 0; j < nElems; j++) // for each element,
            System.out.print(theArray[j] + " "); // display it
        System.out.println("");
    }

    //--------------------------------------------------------------
    public void shellSort() //希尔排序核心代码
    {
        int inner, outer;
        long temp;
        int h = 1; // find initial value of h
        while (h <= nElems / 3) {
         h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)产 生隔
        }
        while (h > 0) // decreasing h, until h=1
        {
            // h-sort the file
            for (outer = h; outer < nElems; outer++) {
                temp = theArray[outer];
                inner = outer;
                // one subpass (eg 0, 4, 8)
                while (inner > h - 1 && theArray[inner - h] >= temp) {
                    theArray[inner] = theArray[inner - h];
                    inner -= h;
                }
                theArray[inner] = temp;
            } // end for
            h = (h - 1) / 3; // decrease h(...,121,40,13,4,1)减少隔
        } // end while(h>0)
    } // end shellSort()
//--------------------------------------------------------------
} // end class ArraySh

////////////////////////////////////////////////////////////////
class ShellSortApp {
    public static void main(String[] args) {
        int maxSize = 10; // array size
        ArraySh arr;
        arr = new ArraySh(maxSize); // create the array
        for (int j = 0; j < maxSize; j++) // fill array with
        { // random numbers
            long n = (int) (java.lang.Math.random() * 99);
            arr.insert(n);
        }
        arr.display(); // display unsorted array
        arr.shellSort(); // shell sort the array
        arr.display(); // display sorted array
    } // end main()
} // end class ShellSortApp
////////////////////////////////////////////////////////////////

希尔排序效率

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。