Shell排序

Shell排序是插入排序的一种改进，为了减小元素移动次数，因为插入排序，每次插入都要将数据依次进行后移，使得效率下降。Shell排序在其基础上增加了增量间隔，每组进行插入排序，直到增量为1，进行直接插入排序后，排序完成。

Shell排序分析起来比较困难，但它的时间复杂度约为O(N*(logN)^2)，比起O(N*logN)的算法要慢，但比起O(N^2)的算法要好一些。

实例代码中间隔选取是采用Knuth 间隔序列 h=h*3+1，而实际间隔选取是多种多样的。

package algorithm;

import static java.lang.Math.random;

public class ShellSort {

    public static void main(String[] args) {
        int maxSize = 16;
        ShellSortArr arr = new ShellSortArr(maxSize);

        for (int i = 0; i < maxSize; i++) {
            int value = (int)(random() * 99);
            arr.insert(value);
        }

        arr.display();
        arr.shellSort();
        arr.display();
    }
}


class ShellSortArr{

    private int theArray[];
    private int nElems;

    public ShellSortArr(int size){
        theArray = new int[size];
        nElems = 0;
    }

    public void insert(int value){
        theArray[nElems] = value;
        nElems++;
    }

    public void display(){
        System.out.print("theArray: ");
        for (int i = 0; i < nElems; i++) {
            System.out.print(theArray[i] + " ");
        }
        System.out.println();
    }

    public void shellSort(){

        // Knuth 间隔序列 h=h*3+1
        // 间隔取值之后需要等于1
        int h = 1;
        while(h <= nElems/3){
            h = h * 3 + 1;
        }

        // 在插入排序的基础上增加间隔，减少移动次数
        while (h > 0){

            for (int i = h; i < nElems; i++) {
                int temp = theArray[i];
                int j = i;

                while(j > h-1 && theArray[j - h] >= temp ){  // 由小到大排序
                    theArray[j] = theArray[j - h];
                    j = j - h;
                }
                theArray[j] = temp;
            }

            h = (h -1)/3;
        }
    }
}