本文簡要記錄常用排序演算法的原理及如何用javascript實現排序功能，具體排序動畫效果查看Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)，看完後思路會非常清晰（請問還有什麼比演算法動態演變更讓人理解？？）。計算機計算是非常機械的，不同於人腦快速找出最值快速排序，必須放慢思路，理清邏輯，關於實現演算法的代碼，建議反覆分析，不同的for循環有不同的結果，每位程序員都有不同的思路，但基本原理都是一致的

  • 冒泡排序
  • 選擇排序
  • 插入排序

冒泡排序Bubble sort

原理：有幾個元素，就循環幾輪，每輪從第一個元素開始，比較相鄰的兩個元素，如果第二個比第一個小，交換位置，繼續比較第二個和第三個，如果第三個比第二個小，交換位置，以此類推，由於在比較大小的過程中，不斷進行位置交換，此時第一輪生成的結果可以看出最大值在最後一個位置，其他元素依次排列，第一輪結束。由於已經產生最大值且位置確定，第二輪的元素個數減一，接著相鄰元素進行對比，產生第二輪最大值且在倒數第二個位置，第二輪結束。以此類推，每輪的元素越來越少，直到只剩一個無法比較，輸出排序後的數組。由於越大的元素會經過不斷的交換慢慢「浮」到數列的頂端，就像冒泡一樣冒到水平面頂部，稱為冒泡排序。

javascript實現：

function BubbleSort(arr){
for(let i = 0 ;i< arr.length;i++){ //輪數
 for(let j = 0 ;j < arr.length - i;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]] //es6語法交換元素
 }
}
}
return arr;
}
console.log(BubbleSort([21,5,10]))

選擇排序Selection Sort

原理：每輪從數組中選出最小的數字，第一輪找到後和第一個數字交換，第二輪從第二個位置開始查找剩餘元素的最小值，與第二個數字交換，以此類推，每次找到最小的元素進行交換，得到最終數列

javascript實現：

function SelectionSort(arr) {
let minIndex;
for (let i = 0; i < arr.length; i++) { //輪數
 minIndex = i;
for (let j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
return arr;
}

插入排序Insection Sort

原理：將第一個元素標記為已排序，遍歷每個沒有排序過的元素，提出當前第一個位置的元素X，將X與排序過的元素從length-1 到 0 進行遍歷，如果某個元素大於X，將排序過的元素向右移一格，否則插入這個元素後面。

javascript實現：

function InsectionSort(arr) {
for (let i = 1; i < arr.length; i++) { //輪數
 let num = arr[i]
for (let j = i - 1; j >= 0; j--) {
if(num < arr[j]){
arr.splice(j,0,num);
arr.splice(j+2,1)
}
}
}
return arr;
}

推薦閱讀：

相關文章