排序算法（Sort）
引言
我們平時對計算機中存儲的數(shù)據(jù)執(zhí)行的兩種最常見的操作就是排序和查找，對于計算機的排序和查找的研究，自計算機誕生以來就沒有停止過。如今又是大數(shù)據(jù)，云計算的時代，對數(shù)據(jù)的排序和查找的速度、效率要求更高，因此要對排序和查找的算法進行專門的數(shù)據(jù)結(jié)構(gòu)設(shè)計，（例如我們上一篇聊到的二叉查找樹就是其中一種），以便讓我們對數(shù)據(jù)的操作更加簡潔高效。
這一篇我們將會介紹一些數(shù)據(jù)排序的基本算法和高級算法并利用JavaScript來逐一實現(xiàn)，讓大伙對計算機中常見的排序算法的思想和實現(xiàn)有基本的了解，起到一個拋磚引玉的作用。
關(guān)于排序算法的說明
在介紹各個算法之前，我們有必要了解一下評估算法優(yōu)劣的一些術(shù)語：
穩(wěn)定：如果a原本在b前面，當a=b時，排序之后a仍然在b的前面
不穩(wěn)定：如果a原本在b的前面，當a=b時，排序之后a可能會出現(xiàn)在b的后面
內(nèi)排序：所有排序操作都在內(nèi)存中完成
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行
時間復(fù)雜度：一個算法執(zhí)行所耗費的時間
空間復(fù)雜度：運行完一個程序所需內(nèi)存的大小
有想要了解更多，關(guān)于時間空間復(fù)雜度的，我推薦一篇文章，請戳這里
基本排序算法
基本排序算法的核心思想就是對一組數(shù)據(jù)按照一定的順序重新排序，其中重排時一般都會用到一組嵌套的 for 循環(huán)，外循環(huán)會遍歷數(shù)組的每一項元素，內(nèi)循環(huán)則用于進行元素直接的比較。
1.冒泡排序（BubbleSort）
冒泡排序是比較經(jīng)典的算法之一，也是排序最慢的算法之一，因為它的實現(xiàn)是非常的容易的。
冒泡排序的算法思想如下（升序排序）：
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣最終最大數(shù)被交換到最后的位置
- 除了最后一個元素以外，針對所有的元素重復(fù)以上的步驟
- 重復(fù)步驟1~3，直到排序完成
下面我借用網(wǎng)上一張動圖，來展示冒泡排序的過程：
具體的JS實現(xiàn)如下：
//冒泡排序
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;
}
我們先設(shè)定一組數(shù)據(jù)，后面我們將都用這組數(shù)據(jù)來測試 :
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( '原始數(shù)據(jù):' + dataStore );
console.log( '冒泡排序:' + bubbleSort( dataStore) );
// 原始數(shù)據(jù):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）
選擇排序是一種比較簡單直觀的排序算法。它的算法思想是，從數(shù)組的開頭開始遍歷，將第一個元素和其他元素分別進行比較，記錄最小的元素，等循環(huán)結(jié)束之后，將最小的元素放到數(shù)組的第一個位置上，然后從數(shù)組的第二個位置開始繼續(xù)執(zhí)行上述步驟。當進行到數(shù)組倒數(shù)第二個位置的時候，所有的數(shù)據(jù)就完成了排序。
選擇排序同樣會用到嵌套循環(huán)，外循環(huán)從數(shù)組第一個位置移到倒數(shù)第二個位置；內(nèi)循環(huán)從第二個位置移動到數(shù)組最后一個位置，查找比當前外循環(huán)所指向的元素還要小的元素，每次內(nèi)循環(huán)結(jié)束后，都會將最小的值放到合適的位置上。
同樣，我借用網(wǎng)上一張動圖，來展示選擇排序的過程 ：
了解了算法思想，具體實現(xiàn)應(yīng)該也不成問題：
//選擇排序
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;
}
它的測試結(jié)果如下：
console.log( '原始數(shù)據(jù):' + dataStore );
console.log( '選擇排序:' + selectionSort( dataStore) );
// 原始數(shù)據(jù):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）
插入排序有點類似人類按字母順序?qū)?shù)據(jù)進行排序，就如同你打撲克牌一樣，將摸來的撲克按大小放到合適的位置一樣。它的原理就是通過嵌套循環(huán)，外循環(huán)將數(shù)組元素挨個移動，而內(nèi)循環(huán)則對外循環(huán)中選中的元素及它后面的元素進行比較；如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小，那么數(shù)組元素會向右移動，為內(nèi)循環(huán)中的這個元素騰出位置。
實現(xiàn)步驟如下：
- 從第一個元素開始，該元素默認已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置
- 重復(fù)步驟2~5，直到排序完成
它的實現(xiàn)效果圖如下：
具體實現(xiàn)代碼如下：
//插入排序
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;
}
排序結(jié)果如下：
console.log( '原始數(shù)據(jù):' + dataStore );
console.log( '插入排序:' + insertionSort( dataStore) );
// 原始數(shù)據(jù):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
我們已經(jīng)學習了三種基本的排序算法，其中冒泡排序是最慢的，插入排序是最快的，我們可以在運行的過程中通過 console.time('sortName') 和 console.timeEnd('sortName') 兩個輸出來看他們的效率如何，我這里給出一組值作為參考，實際中需要大量的數(shù)據(jù)測試和反復(fù)實驗，進行數(shù)理統(tǒng)計后才能被視為有效的統(tǒng)計；
高級排序算法
4.希爾排序（Shell Sort）
我們首先要學習的就是希爾排序，又稱縮小增量排序，這個算法是在插入排序的基礎(chǔ)上做了很大的改善，與插入排序不同的是，它首先會比較位置較遠的元素，而非相鄰的元素。這種方案可以使離正確位置很遠的元素能夠快速回到合適的位置，當算法進行遍歷時，所有元素的間距會不斷的減小，直到數(shù)據(jù)的末尾，此時比較的就是相鄰元素了。
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上有較大提高。
好吧，我還是用個案例來解釋，這樣會更清晰，我們以下面一組數(shù)據(jù)為例：
- 第一次 gap(增量) = 10 / 2 = 5 , 會按照下面進行分組得到五組數(shù)據(jù)（49，13）、（38，27）、（65，49）、（97，55）、（26，4），這樣進行組內(nèi)排序之后（13，49）、（27，38）、（49，65）、（55，97）、（4，26）
此時，數(shù)據(jù)會排成如下結(jié)構(gòu)
- 第二次 gap = 5 / 2 = 2 , 此時可以得到兩個分組，如下
再通過組內(nèi)排序之后，可以得到
- 第三次 gap = 2 / 2 = 1 ， 即不用分組，進行排序后
- 第四次 gap = 1 / 2 = 0 ，即可得到排序完成的數(shù)組
現(xiàn)在，可能對希爾排序有了一定得了解了，用JS實現(xiàn)如下：
//希爾排序
function shallSort(array) {
var increment = array.length;
var i
var temp; //暫存
do {
//設(shè)置增量
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( '原始數(shù)據(jù):' + dataStore );
console.log( '希爾排序:' + shallSort( dataStore) );
// 原始數(shù)據(jù):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）
將兩個的有序數(shù)列合并成一個有序數(shù)列，我們稱之為"歸并"，歸并排序的思想就是將一系列排序好的子序列合并成一個大的完整有序的序列。
實現(xiàn)步驟如下：
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分別采用歸并排序；
- 將兩個排序好的子序列合并成一個最終的排序序列
一張動圖來說明歸并排序的過程：
具體的JS代碼實現(xiàn)如下：
//歸并排序
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;
}
測試結(jié)果如下 ：
console.log( '原始數(shù)據(jù):' + dataStore );
console.log( '希爾排序:' + mergeSort( dataStore) );
// 原始數(shù)據(jù):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）
快速排序是處理大數(shù)據(jù)最快的排序算法之一，它也是一種分而治之的算法，通過遞歸方式將數(shù)據(jù)依次分解為包含較小元素和較大元素的不同子序列，會不斷重復(fù)這個步驟，直到所有的序列全部為有序的，最后將這些子序列一次拼接起來，就可得到排序好的數(shù)據(jù)。
該算法首先要從數(shù)列中選出一個元素作為基數(shù)（pivot）。接著所有的數(shù)據(jù)都將圍繞這個基數(shù)進行，將小于改基數(shù)的元素放在它的左邊，大于或等于它的數(shù)全部放在它的右邊，對左右兩個小數(shù)列重復(fù)上述步驟，直至各區(qū)間只有1個數(shù)。
整個排序過程如下：
具體實現(xiàn)如下：
//快速排序
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 ));
}
測試結(jié)果如下：
console.log( '原始數(shù)據(jù):' + dataStore );
console.log( '快速排序:' + quickSort( dataStore) );
// 原始數(shù)據(jù):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
至此，我們已基本介紹過一些常見的排序算法的思想和具體實現(xiàn)（基數(shù)排序在之前的文章已經(jīng)介紹過，想要了解戳這里），排序算法博大精深，我們不僅要學習理論，也要不斷去實踐，大家加油！
