作者 | 嘉明
來源 | https://github.com/reng99/blogs
排序介紹：
- 一旦我們将資料放置在某個資料結構（比如數組）中存儲起來後，就可以根據需求對資料進行不同方式的排序：
- 比如對姓名按字母排序
- 對商品按照價格排序
- 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 <= outer-1; ++inner){
if(this.arr[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 D
A B E H D 複制
第三次是對H進行操作，因為它比之前的元素都大，是以保持位置。最後一次是對D元素進行插入排序了，過程和最後結果如下：
A B E D H
A B D E H 複制
相關的gif圖了解一下：
gif
相關代碼如下：
insertionSort(){
let temp,
inner,
numElements = this.arr.length;
for(let outer = 1; outer <= numElements-1; outer++){
temp = this.arr[outer];
inner = outer;
while(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循環是互換兩個資料位置
}
}
} 複制
?思考：[6, 0, 2, 9, 3, 5, 8, 0, 5, 4] 間隔為3的排序結果是什麼呢？
歸并排序
原理:
把一系列的排好序的子序列合并成一個大的有序序列。從理論上講，這個算法很容易實作。我們需要兩個排好序的子數組，然後通過比較資料的大小，先從最小的資料開始插入，最後合并得到第三個數組。然而，實際上操作的相當大的資料的時候，使用歸并排序是很耗記憶體的，這裡我們了解一下就行。
merge-sort-gif
實作歸并排序一般有兩種方法，一種是自頂向下和自底向上的方法。
上面的gif圖是自頂向下的方法，那麼何為自頂向下呢？
自頂向下的歸并排序算法就是把數組元素不斷的
二分
，直到子數組的元素個數為一個，因為這個時候子數組必定是有序的，然後再将兩個有序的序列合并成一個新的有序序列，連個有序序列又可以合并成另一個新的有序序列，以此類推，直到合并一個有序的數組。如下圖：
merge-sort-demo1
自底向上的歸并排序算法的思想是将數組先一個一個歸并成兩兩有序的序列，兩兩有序的序列歸并成四個四個有序的序列，以此類推，直到歸并的長度
大于
整個數組的長度，此時整個數組有序。
⚠️注意：數組按照歸并長度劃分，最後一個子數組可能不滿足長度要求，這種情況就要特殊處理了。
merge-sort-demo2
快速排序
快速排序是處理大資料集最快的排序算法之一，時間複雜度 最好的情況也也是和歸并排序一樣，為O(nlogn)。
原理：
快速排序
是一種分而治之（分治）的算法，通過遞歸的方式将資料依次分解為包含較小元素和較大元素的不同子序列，然後不斷重複這個步驟，直到所有的資料都是有序的。
可以更清晰的表達
快速排序算法
步驟如下：
- 選擇一個基準元素（pivot，樞紐），将清單分隔成兩個子序列；
- 對清單重新排序，将所有小于基準值的元素放在基準值的前面，将所有大于基準值的元素放在基準值的後面；
- 分别對較小元素的子序列和較大元素的子序列重複步驟
1 和 2
quicky-sort-gif
我們來用代碼實作下：
// 快速排序
quickSort(){
this.arr = this.quickAux(this.arr);
}
// aux函數 - 快排的輔助函數
quickAux(arr){
let numElements = arr.length;
if(numElements == 0){
return [];
}
let left = [],
right = [],
pivot = arr[0]; // 取數組的第一個元素作為基準值
for(let i = 1; i < numElements; i++){
if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return this.quickAux(left).concat(pivot, this.quickAux(right));
} 複制
搜尋算法
在清單中查找資料又兩種方式：順序查找和二分查找。順序查找适用于元素随機排列的清單；而二分查找适用于元素已排序的清單。二分查找效率更高，但是我們必須在進行查找之前花費額外的時間将清單中的元素進行排序。
順序查找
對于查找資料來說，最簡單的就是從清單中的第一個元素開始對清單元素逐個進行判斷，直到找到了想要的元素，或者直到清單結尾也沒有找到。這種方法稱為
順序查找
或者
線性查找
。
這種查找的代碼實作方式很簡單，如下：
/*
* @param { Array } arr 目标數組
* @param { Number } data 要查找的數組
* @return { Boolean } 是否查找成功
**/
function seqSearch(arr, data){
for(let i = 0; i < arr.length; i++){
if(arr[i] === data){
return true;
}
}
return false;
} 複制
當然，看到上面的代碼，你也許會簡化成下面的這樣的代碼：
function seqSearch(arr, data){
return arr.indexOf(data) >= 0 ? true : false;
} 複制
實作的方式有多種，但是原理都是一樣的，要從第一個元素開始周遊，有可能會周遊到最後一個元素都找不到要查找的元素。是以，這是一種暴力查找技巧的一種。
那麼，有什麼更加高效的查找方法嘛？這就是我們接下來要講的了。
二分查找算法
在開始之前，我們來玩一個猜數字遊戲：
- 規則：在數字1-100之間，你朋友選擇要猜的數字之後，由你來猜數字。你每猜一個數字，你的朋友将會作出下面三種回應之一：
- 猜對了
- 猜大了
- 猜小了
這個遊戲很簡單，如果我們使用二分查找的政策進行的話，我們隻需要經過短短的幾次就确定我們要查找的資料了。
那麼二分查找的原理是什麼呢？
二分查找又稱為折半查找，對
有序的清單
每次進行對半查找。就是這麼簡單@～@！
代碼實作走一波：
/*
* @param { Array } arr 有序的數組 ⚠️注意：是有序的有序的有序的
* @param { Number } data 要查找的資料
* @return { Number } 傳回查找到的位置，未查找到放回-1值
**/
function binSearch(arr, data){
let upperBound = arr.length -1,
lowerBound = 0;
while(lowerBound <= upperBound){
let mid = Math.floor((upperBound + lowerBound) / 2);
if(arr[mid] < data){
lowerBound = mid + 1;
}else if(arr[mid] > data){
upperBound = mid + 1;
}else{
return mid;
}
}
return -1; // 你朋友選要猜的資料在1-100範圍之外
} 複制