【原標題：排序算法歸并排序及其優化 數據結構和算法排序算法】排序介紹：

一旦我們將數據放置在某個數據結構（比如數組）中存儲起來后，就可以根據需求對數據進行不同方式的排序：

比如對姓名按字母排序

對商品按照價格排序

etc.

排序算法又分為簡單排序和高級排序。其中簡單排序包括冒泡排序、選擇排序和插入排序。高級排序包括希爾排序、歸并排序和快速排序。【??這里僅介紹了六種排序算法】

下面我們逐個排序算法來講解下：

冒泡排序之所以叫冒泡排序，是因為使用這種排序算法時，數據值就會像氣泡那樣從數組的一端漂浮到另一端。假設正在將一組數字按照升序排列，較大的值會浮動在數組的右側，而較小的值則會浮動到數組的左側。產生這種冒泡的現象是因為算法會多次在數組中移動過，比較相鄰的數據，當左側值大于右側值的時候將它們互換。

?? 后面講到的排序算法如無說明，則默認為升序

比如下面的簡單列表的例子。

E A D B H

經過第一次的排序后，列表會變成：

A E D B H

前面兩個元素進行了交互。接下來再次排序：

A D E B H

第二個元素和第三個元素進行了交互。繼續進行排序：

A D B E H

第三個元素和第四個元素進行了交換。這一輪最后進行排序：

A D B E H

因為第四個元素比最后一個元素小，所以比較后保持所在位置。反復對第一個元素執行上面的操作（已經固定的值不參與排序，如第一輪固定的H不參與第二輪的比較了），得到如下的最終結果：

A B D E H

相關的動效圖如下：

bubble-sort-gif

關鍵代碼如下：

bubbleSort(){    let numElements = this.arr.length;    for(let outer = numElements-1; outer >= 2; --outer){        for(let inner = 0; inner <=> this.arr[inner+1]){                this.swap(inner, inner+1); // 交換數組兩個元素            }        }    }}

選擇排序選擇排序從數組的開頭開始，將第一個元素和其它元素進行比較。檢查完所有的元素之后，最小的元素會被放在數組的第一個位置，然后算法會從第二個位置繼續。這個過程進行到數組的倒數第二個位置時，所有的數據便完成了排序。

原理：

選擇排序用到雙層嵌套循環。外循環從數組的第一個元素移動到倒數第二個元素；內循環從當前外循環所指元素的第二個元素開始移動到最后一個元素，查找比當前外循環所指元素小的元素。每次內循環迭代后，數組中最小的值都會被賦值到合適的位置。

下面是對五個元素的列表進行選擇排序的簡單例子。初始列表為：

E A D H B

第一次排序會找到最小值，并將它和列表的第一個元素進行交換：

A E D H B

接下查找第一個元素后面的最小值（第一個元素此時已經就位），并對它們進行交換：

A B D H E

D已經就位，因此下一步會對E H進行互換，列表已按順序排列好如下：

A B D E H

通過gif圖可能容易理解：

selection-sort-gif

關鍵代碼如下：

selectionSort(){    let min,        numElements = this.arr.length;    for(let outer = 0; outer <= numElements-2; outer++){        min = outer;        for(let inner = outer+1; inner <= numElements-1; inner++){            if(this.arr[inner] < this.arr[min]){                min = inner;            }        }        this.swap(outer, min);    }}

插入排序插入排序類似我們按照數字或字母的順序對數據進行降序或升序排序整理～

原理：

插入排序也用了雙層的嵌套循環。外循環將數組挨個移動，而內循環則對外循環中選中的元素以及內循環數組后面的那個元素進行比較。如果外循環中選中的元素比內循環中選中的元素要小，那么內循環的數組元素會向右移動，騰出一個位置給外循環選定的元素。

上面表達的晦澀難懂。簡單來說，插入排序就是未排序的元素對已經排序好的序列數據進行合適位置的插入。如果還是不懂，結合下面的排序示例來理解下：

下面對五個元素進行插入排序。初始列表如下：

E B A H D

第一次插入排序，第二個元素挪動到第一位：

B E A H D

第二次插入排序是對A進行操作：

B A E H DA B E H D

第三次是對H進行操作，因為它比之前的元素都大，所以保持位置。最后一次是對D元素進行插入排序了，過程和最后結果如下：

A B E D HA B D E H

相關的gif圖了解一下：

gif

相關代碼如下：

insertionSort(){    let temp,        inner,        numElements = this.arr.length;    for(let outer = 1; outer <= temp="this.arr[outer];" inner=""> 0 && this.arr[inner-1] >= temp){            this.arr[inner] = this.arr[inner-1];            inner--;        }        this.arr[inner] = temp;    }}

希爾排序希爾排序是插入排序的優化版，但是，其核心理念與插入排序不同，希爾排序會首先比較距離較遠的元素，而非相鄰的元素。

原理：

希爾排序通過定義一個間隔序列來表示數據在排序過程中進行比較的元素之間有多遠的間隔。我們可以動態定義間隔序列，不過對于大部分的實際應用場景，算法用到的間隔序列可以提前定義好。

如下演示希爾排序中，間隔序列是如何運行的：

how-hash-sort-run

通過下面的gif圖你也許會更好理解：

hash-sort-gif

實現的代碼：

shellSort(){    let temp,        j,        numElements = this.arr.length;    for(let g = 0; g < this.gaps.length; ++g){        for(let i = this.gaps[g]; i < numElements; ++i){            temp = this.arr[i];            for(j = i; j >= this.gaps[g] && this.arr[j - this.gaps[g]] > temp; j -= this.gaps[g]){ // 之前的已經拍好序的了                this.arr[j] = this.arr[j - this.gaps[g]];            }            this.arr[j] = temp; // 這里和上面的for循環是互換兩個數據位置        }    }}