本文實例講述了JS中的算法與數據結構之常見排序（Sort）算法。分享給大家供大家參考，具體如下：
我們平時對計算機中存儲的數據執行的兩種最常見的操作就是排序和查找，對于計算機的排序和查找的研究，自計算機誕生以來就沒有停止過。如今又是大數據，云計算的時代，對數據的排序和查找的速度、效率要求更高，因此要對排序和查找的算法進行專門的數據結構設計，（例如我們上一篇聊到的二叉查找樹就是其中一種），以便讓我們對數據的操作更加簡潔高效。
這一篇我們將會介紹一些數據排序的基本算法和高級算法并利用JavaScript來逐一實現，讓大伙對計算機中常見的排序算法的思想和實現有基本的了解，起到一個拋磚引玉的作用。
在介紹各個算法之前，我們有必要了解一下評估算法優劣的一些術語：
穩定：如果a原本在b前面，當a=b時，排序之后a仍然在b的前面 不穩定：如果a原本在b的前面，當a=b時，排序之后a可能會出現在b的后面
內排序：所有排序操作都在內存中完成 外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行
時間復雜度：一個算法執行所耗費的時間 空間復雜度：運行完一個程序所需內存的大小
有想要了解更多，關于時間空間復雜度的，我推薦一篇文章，請戳這里
基本排序算法的核心思想就是對一組數據按照一定的順序重新排序，其中重排時一般都會用到一組嵌套的 for 循環，外循環會遍歷數組的每一項元素，內循環則用于進行元素直接的比較。
1.冒泡排序（BubbleSort）
冒泡排序是比較經典的算法之一，也是排序最慢的算法之一，因為它的實現是非常的容易的。
冒泡排序的算法思想如下（升序排序）：
下面我借用網上一張動圖，來展示冒泡排序的過程：
冒泡排序
具體的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）
插入排序有點類似人類按字母順序對數據進行排序，就如同你打撲克牌一樣，將摸來的撲克按大小放到合適的位置一樣。它的原理就是通過嵌套循環，外循環將數組元素挨個移動，而內循環則對外循環中選中的元素及它后面的元素進行比較；如果外循環中選中的元素比內循環中選中的元素小，那么數組元素會向右移動，為內循環中的這個元素騰出位置。
實現步驟如下：
它的實現效果圖如下：
插入排序
具體實現代碼如下：
//插入排序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）
我們首先要學習的就是希爾排序，又稱縮小增量排序，這個算法是在插入排序的基礎上做了很大的改善，與插入排序不同的是，它首先會比較位置較遠的元素，而非相鄰的元素。這種方案可以使離正確位置很遠的元素能夠快速回到合適的位置，當算法進行遍歷時，所有元素的間距會不斷的減小，直到數據的末尾，此時比較的就是相鄰元素了。
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上有較大提高。
好吧，我還是用個案例來解釋，這樣會更清晰，我們以下面一組數據為例：
數據集
第一次分組
此時，數據會排成如下結構
第一次排序
第二次分組
再通過組內排序之后，可以得到
第二次排序
第三次排序
排序完成
現在，可能對希爾排序有了一定得了解了，用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）
將兩個的有序數列合并成一個有序數列，我們稱之為"歸并"，歸并排序的思想就是將一系列排序好的子序列合并成一個大的完整有序的序列。
實現步驟如下：
一張動圖來說明歸并排序的過程：
歸并排序
具體的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
至此，我們已基本介紹過一些常見的排序算法的思想和具體實現（基數排序在之前的文章已經介紹過），排序算法博大精深，我們不僅要學習理論，也要不斷去實踐，大家加油！
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.VeVB.COm/code/HtmlJsRun測試上述代碼運行效果。
PS：這里再為大家推薦一款關于排序的演示工具供大家參考：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.VeVB.COm/aideddesign/paixu_ys
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
