排序演算法是資料結構的入門必修。以下以 JavaScript 實作六種經典排序,並在每段程式碼後附上執行過程的觀察輸出,方便對照理解每一步的變化。
反覆比較相鄰元素並交換,每一輪把當前最大值送到末端,因此得名。
function BubbleSort(array) {
var length = array.length;
// 每一輪縮小一次範圍
for (var i = length - 1; i > 0; i--) {
// 在範圍內進行冒泡,此範圍內最大者將浮到最後
for (var j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
var temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
console.log(array);
console.log("-----------------------------");
}
return array;
}
var arr = [10, 9, 8, 7, 7, 6, 5, 11, 3];
var result = BubbleSort(arr);
console.log(result);
/*
[ 9, 8, 7, 7, 6, 5, 10, 3, 11 ]
[ 8, 7, 7, 6, 5, 9, 3, 10, 11 ]
[ 7, 7, 6, 5, 8, 3, 9, 10, 11 ]
[ 7, 6, 5, 7, 3, 8, 9, 10, 11 ]
[ 6, 5, 7, 3, 7, 8, 9, 10, 11 ]
[ 5, 6, 3, 7, 7, 8, 9, 10, 11 ]
[ 5, 3, 6, 7, 7, 8, 9, 10, 11 ]
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
*/
時間複雜度 O(n²),空間 O(1),穩定。實作時可加上「本輪是否發生交換」的旗標提前結束。
每一輪從未排序區中找出最小值,與該區的第一個位置交換。
function SelectionSort(array) {
var length = array.length;
for (var i = 0; i < length; i++) {
var min = array[i]; // 假定範圍內第一個為最小
var index = i; // 記錄最小值的索引
// 在範圍內挑選真正的最小值
for (var j = i + 1; j < length; j++) {
if (array[j] < min) {
min = array[j];
index = j;
}
}
// 把最小值交換到範圍首位
if (index != i) {
var temp = array[i];
array[i] = array[index];
array[index] = temp;
}
console.log(array);
console.log("---------------------");
}
return array;
}
var arr = [1, 10, 100, 90, 65, 5, 4, 10, 2, 4];
var result = SelectionSort(arr);
console.log(result);
/*
[ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ]
[ 1, 2, 100, 90, 65, 5, 4, 10, 10, 4 ]
[ 1, 2, 4, 90, 65, 5, 100, 10, 10, 4 ]
[ 1, 2, 4, 4, 65, 5, 100, 10, 10, 90 ]
[ 1, 2, 4, 4, 5, 65, 100, 10, 10, 90 ]
[ 1, 2, 4, 4, 5, 10, 100, 65, 10, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
*/
交換次數最少(至多 n-1 次),但比較次數恆為 O(n²),且不穩定。
把待插入元素插入到已排序序列的正確位置,模仿打牌的整理過程。
function InsertionSort(array) {
var length = array.length;
for (var i = 0; i < length - 1; i++) {
// i 代表已排序序列的最後一項索引
var insert = array[i + 1];
var index = i + 1; // 記錄待插入的位置
// 從右向左找出插入點,順便往後搬移
for (var j = i; j >= 0; j--) {
if (insert < array[j]) {
array[j + 1] = array[j];
index = j;
}
}
array[index] = insert;
console.log(array);
console.log("-----------------------");
}
return array;
}
var arr = [100, 90, 80, 62, 80, 8, 1, 2, 39];
var result = InsertionSort(arr);
console.log(result);
/*
[ 90, 100, 80, 62, 80, 8, 1, 2, 39 ]
[ 80, 90, 100, 62, 80, 8, 1, 2, 39 ]
[ 62, 80, 90, 100, 80, 8, 1, 2, 39 ]
[ 62, 80, 80, 90, 100, 8, 1, 2, 39 ]
[ 8, 62, 80, 80, 90, 100, 1, 2, 39 ]
[ 1, 8, 62, 80, 80, 90, 100, 2, 39 ]
[ 1, 2, 8, 62, 80, 80, 90, 100, 39 ]
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
*/
資料近乎有序時接近 O(n),是少數能在小規模或近乎有序資料上打敗 O(n log n) 演算法的排序,且穩定。
插入排序的改良版:以遞減的間隔(gap)先做粗粒度排序,讓元素能長距離移動,最後以 gap=1 收尾。
function ShellSort(array) {
var length = array.length;
var gap = Math.round(length / 2);
while (gap > 0) {
for (var i = gap; i < length; i++) {
var insert = array[i];
var index = i;
for (var j = i; j >= 0; j -= gap) {
if (insert < array[j]) {
array[j + gap] = array[j];
index = j;
}
}
array[index] = insert;
}
console.log(array);
console.log("-----------------------");
gap = Math.round(gap / 2 - 0.1);
}
return array;
}
var arr = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10];
var result = ShellSort(arr);
console.log(result);
/*
[ 13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94 ]
[ 13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94 ]
[ 13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94 ]
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/
時間複雜度依間隔序列而異,通常在 O(n^1.3) 上下;不穩定。它是第一個實用化的超越 O(n²) 的排序演算法。
典型的分治法:把陣列對半拆分直到只剩單一元素,再逐層合併。
function MergeSort(array) {
var length = array.length;
if (length <= 1) {
return array;
} else {
var num = Math.ceil(length / 2);
var left = MergeSort(array.slice(0, num));
var right = MergeSort(array.slice(num, length));
return merge(left, right);
}
}
function merge(left, right) {
console.log(left);
console.log(right);
var a = new Array();
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
a.push(left.shift());
} else {
a.push(right.shift());
}
}
if (left.length > 0) a = a.concat(left);
if (right.length > 0) a = a.concat(right);
console.log(a);
console.log("-----------------------------");
return a;
}
var arr = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10];
var result = MergeSort(arr);
console.log(result);
/*
[ 13 ] [ 14 ] → [ 13, 14 ]
[ 94 ] [ 33 ] → [ 33, 94 ]
[ 13, 14 ] [ 33, 94 ] → [ 13, 14, 33, 94 ]
[ 82 ] [ 25 ] → [ 25, 82 ]
[ 59 ] [ 94 ] → [ 59, 94 ]
[ 25, 82 ] [ 59, 94 ] → [ 25, 59, 82, 94 ]
[ 13, 14, 33, 94 ] [ 25, 59, 82, 94 ] → [ 13, 14, 25, 33, 59, 82, 94, 94 ]
[ 65 ] [ 23 ] → [ 23, 65 ]
[ 45 ] [ 27 ] → [ 27, 45 ]
[ 23, 65 ] [ 27, 45 ] → [ 23, 27, 45, 65 ]
[ 73 ] [ 25 ] → [ 25, 73 ]
[ 39 ] [ 10 ] → [ 10, 39 ]
[ 25, 73 ] [ 10, 39 ] → [ 10, 25, 39, 73 ]
[ 23, 27, 45, 65 ] [ 10, 25, 39, 73 ] → [ 10, 23, 25, 27, 39, 45, 65, 73 ]
[ 13, 14, 25, 33, 59, 82, 94, 94 ] [ 10, 23, 25, 27, 39, 45, 65, 73 ]
→ [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/
時間複雜度穩定為 O(n log n),穩定,但需要 O(n) 的額外空間。上述實作用 shift() 取值,每次都是 O(n) 操作,實務上建議改用索引游標以提升效能。
選一個基準值,把陣列分成「不大於基準」與「大於基準」兩半,再分別遞歸排序。
function QuickSort(array) {
var length = array.length;
if (length <= 1) {
return array;
} else {
var smaller = [];
var bigger = [];
var base = [array[0]];
for (var i = 1; i < length; i++) {
if (array[i] <= base[0]) {
smaller.push(array[i]);
} else {
bigger.push(array[i]);
}
}
console.log(smaller.concat(base.concat(bigger)));
console.log("-----------------------");
return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
}
}
var arr = [8, 10, 100, 90, 65, 5, 4, 10, 2, 4];
var result = QuickSort(arr);
console.log(result);
/*
[ 5, 4, 2, 4, 8, 10, 100, 90, 65, 10 ]
[ 4, 2, 4, 5 ]
[ 2, 4, 4 ]
[ 2, 4 ]
[ 10, 10, 100, 90, 65 ]
[ 90, 65, 100 ]
[ 65, 90 ]
[ 2, 4, 4, 5, 8, 10, 10, 65, 90, 100 ]
*/
平均 O(n log n),不穩定。上述寫法以首元素為基準,在已排序或逆序資料上會退化為 O(n²);實務上可改用隨機基準或三數取中法,並在小区間時遞 cutover 到插入排序。
另外提醒:現代 JavaScript 引擎(V8 等)已為 Array.prototype.sort 做了高度優化,一般只需傳入比較函數即可,無需自行實作;上述程式碼的價值在於理解原理與取捨。