shell排序算法思想

shell排序其實(shí)是插入排序的升級(jí)版，我們可以把數(shù)組分成h組，對(duì)每組 進(jìn)行排序，然后不斷的縮短h,當(dāng)h縮短為1時(shí)就退化成了插入排序。

shell排序算法實(shí)現(xiàn)

 public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
        int[] sortList = shellSort(arr);
        for (int i : sortList) {
            System.out.print(i + "  ");
        }

    }

    /**
     * shell  sort
     *
     * @param arr
     * @return
     */
    private static int[] shellSort(int[] arr) {
        if (arr.length == 0) return null;
        // 計(jì)算出步長(zhǎng)
        int h = 1;
        int N = arr.length;
        while (h < N / 3) h = (h * 3 + 1);
        //控制步長(zhǎng)
        while (h >= 1) {
            //插入排序
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    int temp = arr[j - h];
                    arr[j - h] = arr[j];
                    arr[j] = temp;
                }
            }
            h = h / 3;
        }
        return arr;
    }

算法復(fù)雜度

1.算法的最壞時(shí)間復(fù)雜度為O(n^2)
2.算法的最好時(shí)間復(fù)雜度為O(n)
3.算法的空間復(fù)雜度為O(n)

算法穩(wěn)定性

1 shell排序是不穩(wěn)定的

想看更多完整版請(qǐng)點(diǎn)擊：shell排序