【原標(biāo)題：排序算法歸并排序及其優(yōu)化 數(shù)據(jù)結(jié)構(gòu)和算法排序算法】排序介紹：

一旦我們將數(shù)據(jù)放置在某個(gè)數(shù)據(jù)結(jié)構(gòu)（比如數(shù)組）中存儲(chǔ)起來后，就可以根據(jù)需求對(duì)數(shù)據(jù)進(jìn)行不同方式的排序：

比如對(duì)姓名按字母排序

對(duì)商品按照價(jià)格排序

etc.

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

下面我們逐個(gè)排序算法來講解下：

冒泡排序之所以叫冒泡排序，是因?yàn)槭褂眠@種排序算法時(shí)，數(shù)據(jù)值就會(huì)像氣泡那樣從數(shù)組的一端漂浮到另一端。假設(shè)正在將一組數(shù)字按照升序排列，較大的值會(huì)浮動(dòng)在數(shù)組的右側(cè)，而較小的值則會(huì)浮動(dòng)到數(shù)組的左側(cè)。產(chǎn)生這種冒泡的現(xiàn)象是因?yàn)樗惴〞?huì)多次在數(shù)組中移動(dòng)過，比較相鄰的數(shù)據(jù)，當(dāng)左側(cè)值大于右側(cè)值的時(shí)候?qū)⑺鼈兓Q。

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

比如下面的簡(jiǎn)單列表的例子。

E A D B H

經(jīng)過第一次的排序后，列表會(huì)變成：

A E D B H

前面兩個(gè)元素進(jìn)行了交互。接下來再次排序：

A D E B H

第二個(gè)元素和第三個(gè)元素進(jìn)行了交互。繼續(xù)進(jìn)行排序：

A D B E H

第三個(gè)元素和第四個(gè)元素進(jìn)行了交換。這一輪最后進(jìn)行排序：

A D B E H

因?yàn)榈谒膫€(gè)元素比最后一個(gè)元素小，所以比較后保持所在位置。反復(fù)對(duì)第一個(gè)元素執(zhí)行上面的操作（已經(jīng)固定的值不參與排序，如第一輪固定的H不參與第二輪的比較了），得到如下的最終結(jié)果：

A B D E H

相關(guān)的動(dòng)效圖如下：

bubble-sort-gif

關(guān)鍵代碼如下：

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); // 交換數(shù)組兩個(gè)元素            }        }    }}

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

原理：

選擇排序用到雙層嵌套循環(huán)。外循環(huán)從數(shù)組的第一個(gè)元素移動(dòng)到倒數(shù)第二個(gè)元素；內(nèi)循環(huán)從當(dāng)前外循環(huán)所指元素的第二個(gè)元素開始移動(dòng)到最后一個(gè)元素，查找比當(dāng)前外循環(huán)所指元素小的元素。每次內(nèi)循環(huán)迭代后，數(shù)組中最小的值都會(huì)被賦值到合適的位置。

下面是對(duì)五個(gè)元素的列表進(jìn)行選擇排序的簡(jiǎn)單例子。初始列表為：

E A D H B

第一次排序會(huì)找到最小值，并將它和列表的第一個(gè)元素進(jìn)行交換：

A E D H B

接下查找第一個(gè)元素后面的最小值（第一個(gè)元素此時(shí)已經(jīng)就位），并對(duì)它們進(jìn)行交換：

A B D H E

D已經(jīng)就位，因此下一步會(huì)對(duì)E H進(jìn)行互換，列表已按順序排列好如下：

A B D E H

通過gif圖可能容易理解：

selection-sort-gif

關(guān)鍵代碼如下：

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

插入排序插入排序類似我們按照數(shù)字或字母的順序?qū)?shù)據(jù)進(jìn)行降序或升序排序整理～

原理：

插入排序也用了雙層的嵌套循環(huán)。外循環(huán)將數(shù)組挨個(gè)移動(dòng)，而內(nèi)循環(huán)則對(duì)外循環(huán)中選中的元素以及內(nèi)循環(huán)數(shù)組后面的那個(gè)元素進(jìn)行比較。如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素要小，那么內(nèi)循環(huán)的數(shù)組元素會(huì)向右移動(dòng)，騰出一個(gè)位置給外循環(huán)選定的元素。

上面表達(dá)的晦澀難懂。簡(jiǎn)單來說，插入排序就是未排序的元素對(duì)已經(jīng)排序好的序列數(shù)據(jù)進(jìn)行合適位置的插入。如果還是不懂，結(jié)合下面的排序示例來理解下：

下面對(duì)五個(gè)元素進(jìn)行插入排序。初始列表如下：

E B A H D

第一次插入排序，第二個(gè)元素挪動(dòng)到第一位：

B E A H D

第二次插入排序是對(duì)A進(jìn)行操作：

B A E H DA B E H D

第三次是對(duì)H進(jìn)行操作，因?yàn)樗戎暗脑囟即?，所以保持位置。最后一次是?duì)D元素進(jìn)行插入排序了，過程和最后結(jié)果如下：

A B E D HA B D E H

相關(guān)的gif圖了解一下：

gif

相關(guān)代碼如下：

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

希爾排序希爾排序是插入排序的優(yōu)化版，但是，其核心理念與插入排序不同，希爾排序會(huì)首先比較距離較遠(yuǎn)的元素，而非相鄰的元素。

原理：

希爾排序通過定義一個(gè)間隔序列來表示數(shù)據(jù)在排序過程中進(jìn)行比較的元素之間有多遠(yuǎn)的間隔。我們可以動(dòng)態(tài)定義間隔序列，不過對(duì)于大部分的實(shí)際應(yīng)用場(chǎng)景，算法用到的間隔序列可以提前定義好。

如下演示希爾排序中，間隔序列是如何運(yùn)行的：

how-hash-sort-run

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

hash-sort-gif

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

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]){ // 之前的已經(jīng)拍好序的了                this.arr[j] = this.arr[j - this.gaps[g]];            }            this.arr[j] = temp; // 這里和上面的for循環(huán)是互換兩個(gè)數(shù)據(jù)位置        }    }}