JS中算法之排序算法
1、基本排序算法
1.1、冒泡排序
它是最慢的排序算法之一。
1、不斷比較相鄰的兩個元素，如果前一個比后一個大，則交換位置。
2、當比較完第一輪的時候最后一個元素應該是最大的一個。
3、按照步驟一的方法進行相鄰兩個元素的比較，這個時候由于最后一個元素已經是最大的了，所以第二輪的時候最后一個元素不用比較，此后依次類推。
冒泡排序動圖演示：
function bubbleSort(arr){ for(var i=0; i<arr.length-1; i++ ){ for(var j=0; j<arr.length-1-i ;j++ ){ if(arr[j] > arr[j+1]){ var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
另一種寫法可能更好理解：每一次比較后都拿最小的那個元素放到前面
for (let i = 0; i < ns.length - 1; i++) { for (let j = i + 1; j < ns.length; j++) { let temp; if (ns[i] > ns[j]) { temp = ns[i]; ns[i] = ns[j]; ns[j] = temp; } } }
1.2、選擇排序
從數組的開頭開始，將第一個元素和其他元素進行比較，比較完所有元素后，將最小的元素與第一個元素交換，然后算法會從第二個元素繼續，依次類推。當進行到數組的倒數第二個位置時，所有的數據便完成了排序。
選擇排序動圖演示：
function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //尋找最小的數 minIndex = j; //將最小數的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
1.3、插入排序
從第二個元素開始循環，當前面的元素比選中的元素大時將前面的元素向右移動，直至比較到第1個元素（即索引為0）或者前面的元素不再比選中的大，此時將選中的元素賦值給比它小的元素之后的位置。
插入排序動圖演示：
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; //此時選中的元素 while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; //當比選中的元素大時元素向右移 preIndex--; } arr[preIndex+1] = current; //將選中的元素賦值給比它小的元素之后的位置 } return arr; }
以上的三種基本排序算法中，選擇排序和插入排序要比冒泡排序快，插入排序是這三種算法中最快的
2、高級排序算法
高級排序算法被認為是處理大型數據集的最高效排序算法，它們處理的數據集可以達到上百萬個元素。
2.1、希爾排序
這在插入排序的基礎上做了很大的改善。它會首先比較距離較遠的元素，而非相鄰的元素。比較的元素之間的距離會不斷減小，直至比較的是相鄰元素，此時就是一個直接的插入排序。在開始做最后一次處理時，大部分元素都已經在正確的位置，算法就不必對很多元素進行交換，這就是希爾排序比插入排序更高效的地方。
比如：數組為 [49,38,65,97,26,13,27,49,55,4]，當間隔為5時，將分組為五組數據（49，13）、（38，27）、（65，49）、（97，55）、（26，4），分別對五組數據進行直接的插入排序，然后此時的數組會變為 [13,27,49,55,4,49,38,65,97,26]，依次類推直至間隔為1
通過定義一個間隔序列來表示在排序過程中進行比較的元素之間有多遠的間隔。下面的算法時是動態定義間隔序列。
function shellSort(arr) { var len = arr.length, current, gap = 1; while (gap < len / 3) { //動態定義間隔序列 gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { //間隔在不斷改變，直至為 1 for (var i = gap; i < len; i++) { //從數組索引為間隔大小的位置開始 current= arr[i]; //相當于直接插入排序的選中元素 for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { //間隔序列所間隔開的元素進行直接插入排序 arr[j + gap] = arr[j]; } arr[j + gap] = current; //將選中的元素賦值給比它小的元素之后的位置 } } return arr; }
2.2、歸并排序
歸并排序的實現有兩種方法：1、自上而下（自頂向下）的遞歸 。2、自下而上（自底向上）的迭代
將數據集分解為多組分別只有一個元素的數組，然后通過創建一組左右子數組將它們兩兩有序地合并起來，直到最后合并剩下的兩個大的數組組成有序的完整數組。
歸并排序動圖演示：
function mergeSort(arr) { var len = arr.length; if (len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.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; }
2.3、快速排序
是處理大數據最快的排序算法之一，快速排序算法非常適用于大型數據集合；在處理小數據集時性能反而會下降。
(1) 選擇一個基準元素，將列表分隔成兩個子序列，將所有小于基準值的元素放在基準值的前面，所有大于基準值的元素放在基準值的后面； (2) 分別對較小元素的子序列和較大元素的子序列重復步驟 1
快速排序動圖演示：
function qSort(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 qSort(left).concat(pivot, qSort(right)); //小的元素都放在了基準值的左邊，大的都放在了右邊。小的和大的分別進行了遞歸，結果也是如此，所以完成了排序。 }
3、時間、空間復雜度
插入排序、冒泡排序和選擇排序的時間復雜度為 O(n2)
插入排序、希爾排序、冒泡排序、選擇排序和堆排序的空間復雜度為 O(1)，歸并排序的空間復雜度為 O(n)
3.1、時間復雜度的計算
3.2、空間復雜度的計算
浙公網安備 33010602011771號