技術日新月異,但打好基礎才是持續學習的不竭動力。前陣子閒來無事,為了溫習曾學過的數據結構,我把常見排序算法用 JS 重新實現了一遍,並在文末附上演示,記錄於此與大家分享。
一、簡單排序
冒泡排序
冒泡排序是最直觀的排序算法,時間複雜度為 O(n²):
function bubbleSort(array) { for (var i = 0; i < array.length; i++) { for (var j = array.length; j > 0; j--) { if (array[j] < array[j - 1]) { var temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; } } /* 輸出結果 */ document.write("這是第 + (i + 1) + "次循環·,結果為:"); for (var k = 0; k < array.length; k++) { document.write(array[k] + ","); } document.write("<br />"); /* 輸出結果結束 */ } }直接插入排序
插入排序同屬簡單排序,時間複雜度也是 O(n²),但實際性能略優於冒泡排序:
function insertSort(array) { var temp; for (var i = 1; i < array.length; i++) { var temp = array[i]; for (var j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } array[j] = temp /* 輸出結果 */ document.write("第? + i + "遍排序的結果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 輸出結果結束 */ } }選擇排序
選擇排序也是簡單排序,時間複雜度 O(n²),性能同樣略優於冒泡排序:
function selectSort(array) { var min, temp; ; for (var i = 0; i < array.length; i++) { min = i; for (var j = i + 1; j < array.length; j++) { if (array[min] > array[j]) min = j; } if (min != i) { temp = array[i]; array[i] = array[min]; array[min] = temp; } /* 輸出結果 */ document.write("第 + i + "遍排序的結果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* 輸出結果結束 */ } }二、復雜排序
希爾排序
希爾排序是插入排序的升級版。1959 年,希爾把簡單排序中的「兩兩比較」改為「按步長跳躍式比較」,突破了 O(n²) 的瓶頸。依步長不同,其時間複雜度最好可達 O(n log n),最壞仍是 O(n²):
function shallSort(array) { var increment = array.length; var i var temp; //暫存 var count = 0; 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; /* 輸出結果 */ count++; document.write("<br />第 + count + "遍排序的結果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 輸出結果結束 */ } } } while (increment > 1) }堆排序
堆排序是選擇排序的升級版,通過不斷構建大頂堆或小頂堆,把最大或最小值選到隊列前端。任何情況下其時間複雜度都是 O(n log n):
function heapSort(array) { var temp; var i; for (i = Math.floor(array.length / 2); i >= 0; i--) { heapAdjust(array, i, array.length - 1); //將數組array構建成一個大頂堆 } for (i = array.length - 1; i >= 0; i--) { /*把根節點交換出去*/ temp = array[i]; array[i] = array[0]; array[0] = temp; /*余下的數組繼續構建成大頂堆*/ heapAdjust(array, 0, i - 1); /* 輸出結果 */ document.write("<br />第 + (array.length - i).toString() + "遍排序的結果是:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* 輸出結果結束 */ } } //要調整的子樹 //start為數組開始下標 //max是數組結束下標 function heapAdjust(array, start, max) { var temp, j; temp = array[start];//temp是根節點的值 for (j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得較大孩子的下標 ++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; }歸並排序
歸並排序是復雜排序中唯一的穩定排序,通過不斷「分拆再合並」來完成排序:
//source源數組 //dest目標數組 //s起始下標 //t目標下標 function mSort(source, dest, s, t) { var m; //取中間值 var dest2 = new Array(); if (s == t) { dest[s] = source[s]; } else { m = Math.floor((s + t) / 2); mSort(source, dest2, s, m); mSort(source, dest2, m+1 , t); merge(dest2, dest, s, m, t); /* 輸出結果 */ document.write("<br />第 + ++count + "遍排序的結果是:") for (var n = 0; n < dest.length; n++) { document.write(array[n] + ","); } /* 輸出結果結束 */ } } //將兩個數組按照從小到大的順序融合 //source原數組 //dest排序後的數組 //s第一個下標 //m第二個數組下標 //總長度 function merge(source, dest, s, m, n) { for (var j = m+1, k = s; j <= n && s <= m; k++) { if (source[s] < source[j]) { dest[k] = source[s++]; } else { dest[k] = source[j++]; } } //將剩余排不完的有序數組加入到dest的末端 if (s <= m) { for (var l = 0; l <= m - s; l++) { dest[k + l] = source[s+l]; } } if (j <= n) { for (var l = 0; l <= n - j; l++) { dest[k + l] = source[j+l]; } } }快速排序
快速排序是目前公認最快的排序算法之一,平均時間複雜度為 O(n log n):
var count = 0; function quickSort(array, low, high) { var temp; if (low < high) { var keypoint = QuickSortHelp(array, low, high); count++; document.write("<br />第台? + count + "遍括?排?序ò的?結á果?是?:") for (var l = 0; l < array.length; l++) { document.write(array[l] + ","); } quickSort(array, low, keypoint - 1); quickSort(array, keypoint + 1, high); } } function QuickSortHelp(array, low, high) { while (low < high) { while (low < high && array[low] <= array[high]) { high--; } temp = array[low]; array[low] = array[high]; array[high] = temp; while (low < high && array[low] <= array[high]) { low++ } temp = array[low]; array[low] = array[high]; array[high] = temp; } return low; } 以上就是用 JavaScript 實現的數據結構經典排序算法彙總,涵蓋冒泡、插入、選擇、希爾、堆、歸並、快排等多種算法,希望能給大家一個參考。