作為排序依據的資料項稱為「排序碼」,也就是資料元素的關鍵碼。為了便於查找,我們通常希望資料表按關鍵碼有序——有序表的折半查找效率遠高於線性掃描,而二叉排序樹、B-樹、B+ 樹的建構過程本身就是一個排序過程。
若關鍵碼是主關鍵碼,排序結果唯一;若是次關鍵碼,具有相同關鍵碼的元素之間,前後關係在排序後可能改變。若相同關鍵碼元素的相對位置在排序前後保持一致,稱此排序方法為穩定,否則為不穩定。
排序另可分為兩類:內排序指待排序列完全存放在記憶體中進行,適合規模不大的資料;外排序則在過程中需要存取外部儲存媒體,適用於大到無法全部放入記憶體的序列。
/** @name 氣泡排序
* @desc 比較排序,複雜度 O(n*n)
*/
function BubbleSort(list) {
var len = list.length;
var cl, temp;
while (len--) {
cl = list.length;
while (cl--) {
if (list[cl] > list[len] && cl < len) {
temp = list[len];
list[len] = list[cl];
list[cl] = temp;
}
}
}
return list;
}
/** @name 快速排序
* @desc 比較排序,最差 O(n*n),最佳 O(nlogn)
*/
function QuickSort(list) {
var i = 0;
var j = list.length;
var len = j;
var left, right;
var k = findK(i, j);
if (k != 0) {
var leftArr = [];
var rightArr = [];
var midArr = [list[k]];
while (len--) {
if (len != k) {
if (list[len] > list[k]) {
rightArr.push(list[len]);
} else {
leftArr.push(list[len]);
}
}
}
left = QuickSort(leftArr);
right = QuickSort(rightArr);
list = left.concat(midArr).concat(right);
}
return list;
}
function findK(i, j) {
// 預設取中間位置作為基準
return Math.floor((i + j) / 2);
}
快速排序的核心思想是分治:把待排序序列切成兩塊,从而降低整體複雜度;遞迴的巧用則是它的精妙之處。流程是先用 findK 找出一個基準元素,其餘元素與之比較,較大的收進一個集合、較小的收進另一個,再分別對兩集合排序。
它的效率主要取決於 findK 的實作與待排序資料的有序程度——基準選得越均勻,分割越平衡。也因為相同元素的相對位置會被打散,快速排序是不穩定的排序法。
所有基於比較的排序法都有一個共同天花板:無論怎麼優化,平均排序時間必然隨元素數量增加而上升。非比較排序試圖繞過這個限制,讓時間複雜度趨向一個與資料量無關的穩定值,桶排序就是代表。
/** @name 桶排序
* @desc 非比較排序
*/
function BucketSort(list) {
var len = list.length;
var range = findMax(list);
var result = [],
count = [];
var i, j;
for (i = 0; i < range; i++) {
count.push(0);
}
for (j = 0; j < len; j++) {
count[list[j]]++;
result.push(0);
}
for (i = 1; i < range; i++) {
count[i] = count[i - 1] + count[i];
}
for (j = len - 1; j >= 0; j--) {
result[count[list[j]]] = list[j];
count[list[j]]--;
}
return result;
}
function findMax(list) {
return MAX;
}
運作方式:先初始化一個長度為 MAX 的 count 陣列,把每個元素依其值放進對應位置並計數;接著累加 count,使第 n 個元素的值等於「值為 n 的元素在排序後的落點」;最後反向把元素映射進結果陣列。
桶排序的巧思在於:若一個元素在集合中是第 n 大,它就該排在第 n 位,完全不必關心前一位或後一位比它大還是小,也就是完全不必比較。
代價也很明顯:實務上資料值的範圍往往遠大於元素數量,因此必須配置一個巨大的 count 陣列。這也是為什麼桶排序的常見場景是外排序,而非記憶體內的一般排序。
有興趣的話,可以自己動手量測這三種排序在不同資料規模下的耗時曲線,會對「複雜度」這個概念有更直觀的體會。