希爾排序java實作

思想

shell排序是對直接插入排序的改進，我們已經知道，直接插入排序的複雜度受本身序列的有序程度影響，當數組已經有序，則每次查找插入的位置時間O（1），總的複雜度O（n），而當逆序對較多時，或者全部全部逆序時，複雜度為O（n^2）。是以希爾排序的思想是先優化子序列的有序程度，慢慢增大序列長度，最後對整個數組排序。

步驟

1、确定增量序列

2、按照增量序列分組，對每組進行直接插入排序（以第一個子序列的第二進制素開始，向前面尋找更大的元素，沒有則停下來）

3、重複1，直到增量為1

代碼實作

class ShellSort{
    public static void main(String[] args) {
        int[] a={100,50,9,3, 4, 10, 3, 6, 7, 4, 1, 2};
        int n=a.length;
        int gap=n;
        while (gap>1){//最小間隔是1
            gap=gap/2;//最優增量縮減序列選擇不确定，1/2是希爾建議的方式
            //其實下面的跟直接插入排序差不多，差別是開始索引是gap，查找間隔是gap
            for (int i=gap;i<n;i++){
                int k=a[i];//新元素
                int start=i-gap;//待比較元素
                while (start>=0&&a[start]>k){//大的往後移
                    a[start+gap]=a[start];
                    start-=gap;//間隔是gap
                }
                a[start+gap]=k;//把k放到合适的位置
            }
        }
        for (int i:a){
            System.out.print(i+" ");
        }
    }
}
           

算法分析

注意我們在每次對每個分組排序的時候不是分别對每個組分開排序，而是仍然從前往後掃描，那麼顯然，我們每次直接插入排序的key從每次的第一個子序列的第二個元素開始（與直接插入排序同理），然後挨個往後走，每個元素屬于哪個組，我們就把它在其所在組進行直接插入排序。有點繞，仔細想想就好啦。

平均時間複雜度：o(N1.3)，大量資料研究表明在o(N1.3)附近，事實上也不是嚴格論證的結果。

最好時間複雜度：仍然和增量序列的選取有關。

最壞時間複雜度：o(N^2)。

空間複雜度：o(1)隻有常數個輔助變量。

穩定性：不穩定，例如待排序列（3，2，2，1），取d=2時，顯然就能看出是不穩定的