[[429028]]

1959年Shell發(fā)明，第一個(gè)突破 O(n^2^) 的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。

插入排序

插入排序的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入

代碼實(shí)現(xiàn)：

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; 
} 

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

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n^2^)
• 空間復(fù)雜度：O(1)

希爾排序

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

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

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

希爾排序又是如何優(yōu)化的喃?

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

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

那我們有是如何進(jìn)行分組喃?

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

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

例如：

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

排序前：

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

第一趟排序：

對(duì)三組數(shù)據(jù)分別進(jìn)行插入排序，因此我們?nèi)齻€(gè)數(shù)組得到的結(jié)果為：[1, 4] ， [5, 8] ， [3, 7]

此時(shí)數(shù)組是這樣子的：[1, 4, 5, 8, 3, 7]

第二趟排序：

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

代碼實(shí)現(xiàn)：

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; 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(1)