算法系列「希爾排序」篇

常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。用一張圖概括：

關於時間複雜度：

1. 平方階 (O(n2)) 排序各類簡單排序：直接插入、直接選擇和冒泡排序。

2. 線性對數階 (O(nlog2n)) 排序快速排序、堆排序和歸併排序；

3. O(n1+§))排序，§ 是介於 0 和 1 之間的常數。希爾排序

4. 線性階 (O(n)) 排序基數排序，此外還有桶、箱排序。

關於穩定性：

穩定的排序算法：冒泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k：“桶”的個數

In-place：佔用常數內存，不佔用額外內存

Out-place：佔用額外內存

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同

希爾排序

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；

• 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

1. 算法步驟

1. 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個數 k，對序列進行 k 趟排序；

3. 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

2. JavaScript 代碼實現

functionshellSort(arr) {
    var len =arr.length,
        temp,
        gap =1;
    while(gap < len/3) { //動態定義間隔序列
        gap =gap*3+1;
    }
    for (gap; gap >0; gap =Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
 temp = arr[i];
 for (var j = i-gap; j >=0&& arr[j] > temp; j-=gap) {
 arr[j+gap] = arr[j];
 }
 arr[j+gap] = temp;
        }
    }
    return arr;
}
 

3. Python 代碼實現

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
 temp = arr[i]
 j = i-gap
 while j >=0 and arr[j] > temp:
 arr[j+gap]=arr[j]
 j-=gap
 arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}
 

4. Go 代碼實現

func shellSort(arr []int) int {
 length := len(arr)
 gap := 1
 for gap < gap/3 {
 gap = gap*3 + 1
 }
 for gap > 0 {
 for i := gap; i < length; i++ {
 temp := arr[i]
 j := i - gap
 for j >= 0 && arr[j] > temp {
 arr[j+gap] = arr[j]
 j -= gap
 }
 arr[j+gap] = temp
 }
 gap = gap / 3
 }
 return arr
}

5.Java代碼實現

public void shellSort(int[] list) {
    int gap = list.length / 2;
 
    while (1 <= gap) {
        // 把距離為 gap 的元素編為一個組，掃描所有組
        for (int i = gap; i < list.length; i++) {
 int j = 0;
 int temp = list[i];
 
 // 對距離為 gap 的元素組進行排序
 for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
 list[j + gap] = list[j];
 }
 list[j + gap] = temp;
        }
 
        System.out.format("gap = %d:\t", gap);
        printAll(list);
        gap = gap / 2; // 減小增量
    }
}