排序算法（Sort）
引言
我們平時對計算機中存儲的資料執行的兩種最常見的操作就是排序和查找，對于計算機的排序和查找的研究，自計算機誕生以來就沒有停止過。如今又是大資料，雲計算的時代，對資料的排序和查找的速度、效率要求更高，是以要對排序和查找的算法進行專門的資料結構設計，（例如我們上一篇聊到的二叉查找樹就是其中一種），以便讓我們對資料的操作更加簡潔高效。
這一篇我們将會介紹一些資料排序的基本算法和進階算法并利用JavaScript來逐一實作，讓大夥對計算機中常見的排序算法的思想和實作有基本的了解，起到一個抛磚引玉的作用。
關于排序算法的說明
在介紹各個算法之前，我們有必要了解一下評估算法優劣的一些術語：
穩定：如果a原本在b前面，當a=b時，排序之後a仍然在b的前面
不穩定：如果a原本在b的前面，當a=b時，排序之後a可能會出現在b的後面
内排序：所有排序操作都在記憶體中完成
外排序：由于資料太大，是以把資料放在磁盤中，而排序通過磁盤和記憶體的資料傳輸才能進行
時間複雜度：一個算法執行所耗費的時間
空間複雜度：運作完一個程式所需記憶體的大小
有想要了解更多，關于時間空間複雜度的，我推薦一篇文章，請戳這裡這裡
基本排序算法
基本排序算法的核心思想就是對一組資料按照一定的順序重新排序，其中重排時一般都會用到一組嵌套的 for 循環，外循環會周遊數組的每一項元素，内循環則用于進行元素直接的比較。
1.冒泡排序（BubbleSort）
冒泡排序是比較經典的算法之一，也是排序最慢的算法之一，因為它的實作是非常的容易的。
冒泡排序的算法思想如下（升序排序）：
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣最終最大數被交換到最後的位置
- 除了最後一個元素以外，針對所有的元素重複以上的步驟
- 重複步驟1~3，直到排序完成
下面我借用網上一張動圖，來展示冒泡排序的過程：
冒泡排序
具體的JS實作如下：
//冒泡排序
function bubbleSort ( data ) {
var temp = 0;
for ( var i = data.length ; i > 0 ; i -- ){
for( var j = 0 ; j < i - 1 ; j++){
if( data[j] > data[j + 1] ){
temp = data[j];
data[j] = data [j+1];
data[j+1] = temp;
}
}
}
return data;
}
我們先設定一組資料，後面我們将都用這組資料來測試 :
var dataStore = [ 72 , 1 , 68 , 95 , 75 , 54 , 58 , 10 , 35 , 6 , 28 , 45 , 69 , 13 , 88 , 99 , 24 , 28 , 30 , 31 , 78 , 2 , 77 , 82 , 72 ];
console.log( '原始資料:' + dataStore );
console.log( '冒泡排序:' + bubbleSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 冒泡排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
2.選擇排序（SelctionSort）
選擇排序是一種比較簡單直覺的排序算法。它的算法思想是，從數組的開頭開始周遊，将第一個元素和其他元素分别進行比較，記錄最小的元素，等循環結束之後，将最小的元素放到數組的第一個位置上，然後從數組的第二個位置開始繼續執行上述步驟。當進行到數組倒數第二個位置的時候，所有的資料就完成了排序。
選擇排序同樣會用到嵌套循環，外循環從數組第一個位置移到倒數第二個位置；内循環從第二個位置移動到數組最後一個位置，查找比目前外循環所指向的元素還要小的元素，每次内循環結束後，都會将最小的值放到合适的位置上。
同樣，我借用網上一張動圖，來展示選擇排序的過程 ：
選擇排序
了解了算法思想，具體實作應該也不成問題：
//選擇排序
function selectionSort( data ) {
for( var i = 0; i< data.length ; i++){
var min = data[i];
var temp;
var index = i;
for( var j = i + 1; j< data.length; j++){
if( data[j] < min ){
min = data[j];
index = j;
}
}
temp = data[i];
data[i] = min;
data[index]= temp;
}
return data;
}
它的測試結果如下：
console.log( '原始資料:' + dataStore );
console.log( '選擇排序:' + selectionSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 選擇排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
3.插入排序（insertionSort）
插入排序有點類似人類按字母順序對資料進行排序，就如同你打撲克牌一樣，将摸來的撲克按大小放到合适的位置一樣。它的原理就是通過嵌套循環，外循環将數組元素挨個移動，而内循環則對外循環中選中的元素及它後面的元素進行比較；如果外循環中選中的元素比内循環中選中的元素小，那麼數組元素會向右移動，為内循環中的這個元素騰出位置。
實作步驟如下：
- 從第一個元素開始，該元素預設已經被排序
- 取出下一個元素，在已經排序的元素序列中從後向前掃描
- 如果該元素（已排序）大于新元素，将該元素移到下一位置
- 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到該位置
- 重複步驟2~5，直到排序完成
它的實作效果圖如下：
插入排序
具體實作代碼如下：
//插入排序
function insertionSort( data ) {
var len = data.length;
for (var i = 1; i < len; i++) {
var key = data[i];
var j = i - 1;
while ( j >= 0 && data[j] > key) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = key;
}
return data;
}
排序結果如下：
console.log( '原始資料:' + dataStore );
console.log( '插入排序:' + insertionSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 插入排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
我們已經學習了三種基本的排序算法，其中冒泡排序是最慢的，插入排序是最快的，我們可以在運作的過程中通過 console.time('sortName') 和 console.timeEnd('sortName') 兩個輸出來看他們的效率如何，我這裡給出一組值作為參考，實際中需要大量的資料測試和反複實驗，進行數理統計後才能被視為有效的統計；
排序時間比較
進階排序算法
4.希爾排序（Shell Sort）
我們首先要學習的就是希爾排序，又稱縮小增量排序，這個算法是在插入排序的基礎上做了很大的改善，與插入排序不同的是，它首先會比較位置較遠的元素，而非相鄰的元素。這種方案可以使離正确位置很遠的元素能夠快速回到合适的位置，當算法進行周遊時，所有元素的間距會不斷的減小，直到資料的末尾，此時比較的就是相鄰元素了。
該方法的基本思想是：先将整個待排元素序列分割成若幹個子序列（由相隔某個“增量”的元素組成的）分别進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，是以希爾排序在時間效率上有較大提高。
好吧，我還是用個案例來解釋，這樣會更清晰，我們以下面一組資料為例：
資料集
- 第一次 gap(增量) = 10 / 2 = 5 , 會按照下面進行分組得到五組資料（49，13）、（38，27）、（65，49）、（97，55）、（26，4），這樣進行組内排序之後（13，49）、（27，38）、（49，65）、（55，97）、（4，26）
第一次分組
此時，資料會排成如下結構
第一次排序
- 第二次 gap = 5 / 2 = 2 , 此時可以得到兩個分組，如下
第二次分組
再通過組内排序之後，可以得到
第二次排序
- 第三次 gap = 2 / 2 = 1 ， 即不用分組，進行排序後
第三次排序
- 第四次 gap = 1 / 2 = 0 ，即可得到排序完成的數組
排序完成
現在，可能對希爾排序有了一定得了解了，用JS實作如下：
//希爾排序
function shallSort(array) {
var increment = array.length;
var i
var temp; //暫存
do {
//設定增量
increment = Math.floor(increment / 3) + 1;
for (i = increment ; i < array.length; i++) {
if ( array[i] < array[i - increment]) {
temp = array[i];
for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
array[j + increment] = array[j];
}
array[j + increment] = temp;
}
}
}
while (increment > 1)
return array;
}
效果如下：
console.log( '原始資料:' + dataStore );
console.log( '希爾排序:' + shallSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希爾排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
5.歸并排序（Merge Sort）
将兩個的有序數列合并成一個有序數列，我們稱之為"歸并"，歸并排序的思想就是将一系列排序好的子序列合并成一個大的完整有序的序列。
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分别采用歸并排序；
- 将兩個排序好的子序列合并成一個最終的排序序列
一張動圖來說明歸并排序的過程：
歸并排序
具體的JS代碼實作如下：
//歸并排序
function mergeSort ( array ) {
var len = array.length;
if( len < 2 ){
return array;
}
var middle = Math.floor(len / 2),
left = array.slice(0, middle),
right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
測試結果如下 ：
console.log( '原始資料:' + dataStore );
console.log( '希爾排序:' + mergeSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希爾排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
6.快速排序（Quicksort）
快速排序是處理大資料最快的排序算法之一，它也是一種分而治之的算法，通過遞歸方式将資料依次分解為包含較小元素和較大元素的不同子序列，會不斷重複這個步驟，直到所有的序列全部為有序的，最後将這些子序列一次拼接起來，就可得到排序好的資料。
該算法首先要從數列中選出一個元素作為基數（pivot）。接着所有的資料都将圍繞這個基數進行，将小于改基數的元素放在它的左邊，大于或等于它的數全部放在它的右邊，對左右兩個小數列重複上述步驟，直至各區間隻有1個數。
整個排序過程如下：
快速排序
具體實作如下：
//快速排序
function quickSort( arr ){
if ( arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push( arr[i] );
} else {
right.push( arr[i] );
}
}
return quickSort( left ).concat( pivot, quickSort( right ));
}
測試結果如下：
console.log( '原始資料:' + dataStore );
console.log( '快速排序:' + quickSort( dataStore) );
// 原始資料:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 快速排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
至此，我們已基本介紹過一些常見的排序算法的思想和具體實作（基數排序在之前的文章已經介紹過，想要了解戳這裡），排序算法博大精深，我們不僅要學習理論，也要不斷去實踐，大家加油！
作者：Cryptic
連結：http://www.jianshu.com/p/8d30da8b832e
來源：簡書
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。