希爾排序法

• 希爾排序也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。
  是基於插入排序的以下兩點性質而提出改進方法的：

1. 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序O(n)的效率
2. 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位

程式範例試做:

import java.util.Arrays;

public class Alex1010_1 {
    public static void main(String[] args) {
        int [] arr = {86,68,42,26,82,48,84,75,79,11,16,45,9,54,32};
        Alex1010_1(arr);
    }

    public static void Alex1010_1(int [] arr) {
        int temp = 0; // 用來保存當前的數值
        int step = arr.length /2 ; // 步長為陣列長度除以2
        int count = 0; // 用於紀錄做了幾輪排序而已,不重要
        while (step >= 1) {
            for(int i = step; i < arr.length; i++) {
                // 遍歷各組中所有的元素 , 步長為 arr.length/2
                for(int j = i - step; j >= 0; j -= step) {
                    // 如果當前元素大於加上步長後的那個元素,說明需要交換
                    if(arr[j] > arr[j+step]) {
                        temp = arr[j];
                        arr[j] = arr[j+step];
                        arr[j+step] = temp;
                    }
                }
            }
            step = step / 2; // 每輪步長再繼續除以2
            count++;
            System.out.println("第 "+(count)+" 輪希爾排序後為 "+Arrays.toString(arr));
        }
    }
}

程式執行結果:

第 1 輪希爾排序後為 [79, 11, 16, 26, 9, 48, 32, 75, 86, 68, 42, 45, 82, 54, 84]
第 2 輪希爾排序後為 [9, 11, 16, 26, 79, 48, 32, 45, 82, 54, 42, 75, 86, 68, 84]
第 3 輪希爾排序後為 [11, 9, 16, 26, 32, 45, 42, 48, 79, 54, 82, 68, 84, 75, 86]
第 4 輪希爾排序後為 [9, 11, 16, 26, 32, 42, 45, 48, 54, 68, 75, 79, 82, 84, 86]

以上為希爾排序法的交換式，經過速度測試可以發現，當處理多份資料時，運行的處理時間延長了很多，原因就是因為這個交換的部分，由於插入排序法式移動式的，所以這樣並沒有真正使用到插入排序法，因此我們可以對此進行改進並優化。

程式範例試做:

import java.util.Arrays;

public class Alex1010_2 {
    public static void main(String[] args) {
        int[] arr = {86,68,42,26,82,48,84,75,79,11,16,45,9,54,32};
        Alex1010_2(arr);
    }

    public static void Alex1010_2(int[] arr) {
        int temp = 0;
        int step = arr.length / 2;
        int count = 0;
        int j;

        while (step >= 1) {
            for (int i = step; i < arr.length; i++) {
                j = i;
                temp = arr[j];
                if (arr[j] < arr[j - step]) {
                    while (j - step >= 0 && temp < arr[j - step]) {
                        //移動
                        arr[j] = arr[j - step];
                        j -= step;
                    }
                    // 當退出while循環,就給temp找到插入的位置
                    arr[j] = temp;
                }
            }
            step = step / 2;
            count++;
            System.out.println("第 " + (count) + " 輪希爾排序後為 " + Arrays.toString(arr));
        }
    }
}

程式執行結果:

第 1 輪希爾排序後為 [32, 68, 11, 16, 45, 9, 54, 75, 79, 42, 26, 82, 48, 84, 86]
第 2 輪希爾排序後為 [16, 26, 9, 32, 45, 11, 42, 68, 79, 48, 75, 82, 54, 84, 86]
第 3 輪希爾排序後為 [9, 11, 16, 26, 32, 42, 45, 48, 54, 68, 75, 79, 82, 84, 86]

時間複雜度

最佳：O(n)
平均：O(n²)
最差：O(n⁵/⁴)

由執行結果可見，不僅是減少排序時間，連排序的輪數都減少了。