[[429028]]

1959年Shell發明，第一個突破 O(n^2^) 的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。

插入排序

插入排序的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入

代碼實現：

function insertionSort(arr) { 
    let n = arr.length; 
    let preIndex, current; 
    for (let i = 1; i < n; i++) { 
        preIndex = i - 1; 
        current = arr[i]; 
        while (preIndex >= 0 && arr[preIndex] > current) { 
            arr[preIndex + 1] = arr[preIndex]; 
            preIndex--; 
        } 
        arr[preIndex + 1] = current; 
    } 
    return arr; 
} 

插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。

復雜度分析：

• 時間復雜度：O(n^2^)
• 空間復雜度：O(1)

希爾排序

回顧一下上面的插入排序：

• 第一趟插入排序后，我們得到的有效序列長度為 2
• 第二趟插入排序后，我們得到的有效序列長度為 3
• ...
• 直到這個序列有序

所以，如果序列足夠亂的話，時間復雜度為 O(n^2^)

希爾排序又是如何優化的喃?

希爾排序又叫縮小增量排序，就是把數列進行分組(組內不停使用插入排序)，直至從宏觀上看起來有序，最后插入排序起來就容易了(無須多次移位或交換)。

其中組的數量稱為 增量 ，顯然的是，增量是不斷遞減的(直到增量為1)

那我們有是如何進行分組喃?

往往的： 如果一個數列有 8 個元素，我們第一趟的增量是 4 ，第二趟的增量是 2 ，第三趟的增量是 1 。如果一個數列有 18 個元素，我們第一趟的增量是 9 ，第二趟的增量是 4 ，第三趟的增量是2 ，第四趟的增量是 1

很明顯我們可以用一個序列來表示增量：n/2、(n/2)/2、...、1，每次增量都/2

例如：

let arr = [4, 1, 5, 8, 7, 3] 

排序前：

將該數組看成三組( Math.floor(arr.length/2) )，分別是：[4, 1] ， [5, 8] ， [7, 3]

第一趟排序：

對三組數據分別進行插入排序，因此我們三個數組得到的結果為：[1, 4] ， [5, 8] ， [3, 7]

此時數組是這樣子的：[1, 4, 5, 8, 3, 7]

第二趟排序：

• 增量減少了，上面增量是 3 ，此時增量應該為 1 了，因此把 [1, 4, 5, 8, 3, 7] 看成一個數組(從宏觀上是有序的了)，對其進行插入排序，直至有序

代碼實現：

function shellSort(arr) { 
    let n = arr.length; 
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) { 
        for (let i = gap; i < n; i++) { 
            let j = i; 
            let current = arr[i]; 
            while (j - gap >= 0 && current < arr[j - gap]) { 
                 arr[j] = arr[j - gap]; 
                 j = j - gap; 
            } 
            arr[j] = current; 
        } 
    } 
    return arr; 
} 

復雜度分析：

• 時間復雜度：O(nlogn)
• 空間復雜度：O(1)