氣泡排序的原理是讓最大或最小的元素「浮」起來。插入排序、選擇排序、快速排序、氣泡排序都屬於比較排序。
思路:依序比較相鄰的兩個數,小的放前、大的放後。第一趟從第一對比較到最後一對,把最大的數送到末尾;第二趟再從頭比較到倒數第二個(末尾已就位),如此反覆,直到完成排序。由於小的不斷往前、大的往後,就像氣泡上升,故名氣泡排序。
實作時要注意三點:一是交換可用 a=[b,b=a][0] 這個巧妙寫法,取代傳統的暫存變數;二是快取 array.length 避免重複取值;三是內層迴圈要從第一個數比較到倒數第 n 個。
function bubbleSort(array) {
var l=array.length;
for (var i = 0; i < l; i++) {
for (var j = 0; j < l-i; j++) {
if (array[j] < array[j - 1]) {
array[j] = [array[j - 1], array[j - 1] = array[j]][0]// 交換元素
}
}
}
}

非常直觀,就像摸牌、插牌的過程。思路:先假設手裡有一張已排好的牌,取出下一張 a,從後往前掃描已排序的牌,若某張比 a 大就往後挪出空間,直到找到不大於 a 的位置插入,然後重複。
function insert(arr) {
var l = arr.length;
var empty = [];// 空陣列,表示我們的手
empty.push(arr[0]);// 先摸起來一張
for (var i = 1; i < l; i++) {
if (arr[i] > empty[empty.length - 1]) {
empty[empty.length] = arr[i]
}
for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) {
empty[j] = empty[j - 1];// 向右移動
empty[j - 1] = arr[i];// 放到空出來的位置
}
}
return empty
}
這裡 && 表示「且」,兩邊條件都成立才成立,也能用來取代簡單的 if。另外要記得:陣列 arr 的「最後一項」是 arr[arr.length-1]。
思路:在未排序區找出最小元素放到已排序序列的起始位置,再從剩餘元素找次小的放到末尾,以此類推。實作時用一個變數記錄目前最小值的索引,遍歷後與起始位置交換。
function selectSort(array) {
var min;
var l = array.length;
for (var i = 0; i < l; i++) {
min = i;
for (var j = i + 1; j < l; j++) {
if (array[min] > array[j])
min = j;
}
if (min != i) {
array[i]= [array[min],array[min]=array[i]][0];// 交換元素
}
}
return array;
}

快速排序是目前最強大的排序演算法,運用了遞迴。思路:從陣列挑出一個「基準」值,比它小的放左邊、比它大的放右邊,得到「左陣列 + 基準 + 右陣列」,再對左右兩邊套用同樣的處理,直到子陣列長度不足以再分為止。
function quickSort(arr) {
var l = arr.length;
if(arr.length <= 1){return arr};
var num = Math.floor(arr.length / 2);
var numValue = arr.splice(num, 1)[0];// 取一個元素出來
var left = [];
var right = [];
for (var i = 0; i < l; i += 1) {
arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]);
}
return quickSort(left).concat([numValue], quickSort(right))
}
這裡要注意 arr.splice(num,1) 雖然只取一個數,但結果仍是陣列,需要 [0] 取出,否則會出現一堆巢狀陣列。

以上四種演算法除了快速排序外都屬於簡單排序,而它們在面試中考得非常頻繁。要特別強調的是,這些演算法大量運用了迴圈與陣列操作,務必熟記。