演算法並不是某個語言的專利。下面整理的這幾個基礎案例用 JavaScript 描述,但它們的思路放在 Java、C、Python 裡同樣成立,適合剛入門或想複習資料結構的朋友收藏起來慢慢看。
最直觀的一種查找:從頭到尾逐個比對,找到就回傳索引,全部掃完沒命中則回傳 -1。它是理解「時間複雜度」最好的起點。
//A為數組,x為要搜索的值
function linearSearch(A, x) {
for (var index = 0; index < A.length; index++) {
if (A[index] == x) {
return index;
}
}
return -1;
}
又稱折半查找,前提很關鍵:資料必須已經排好序。每次拿中間元素與目標比較,把範圍砍掉一半,因此在大量資料上遠快於線性查找。實作時記得取整,並小心 low、high 的邊界。
//A為已按"升序排列"的數組,x為要查詢的元素
//返回目標元素的下標
function binarySearch(A, x) {
var low = 0, high = A.length - 1;
while (low <= high) {
var mid = Math.floor((low + high) / 2); //下取整
if (x == A[mid]) {
return mid;
}
if (x < A[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
相鄰兩兩比較、把大的往後推,每一輪都能把當前最大值「浮」到尾端。這裡有兩個小細節值得學:內層迴圈是倒著走的,另外用一個 sorted 旗標做提前結束的優化——如果某一輪完全沒有發生交換,代表資料已經有序,可以直接收工。
//冒泡排序
function bubbleSort(A) {
for (var i = 0; i < A.length; i++) {
var sorted = true; //注意:內循環是倒著來的
for (var j = A.length - 1; j > i; j--) {
if (A[j] < A[j - 1]) {
swap(A, j, j - 1);
sorted = false;
}
}
if (sorted) {
return;
}
}
}
像整理撲克牌一樣:假設左邊已經排好,先把自己手上的牌空出一個位置,前面比它大的元素依次往後挪,直到讓出一個「坑」,再把目標元素放進去。資料量小或接近有序時,它的表現往往比更複雜的排序更好。
//插入排序
//假定當前元素之前的元素已經排好序,先把自己的位置空出來,
//然後前面比自己大的元素依次向後移,直到空出一個"坑",
//然後把目標元素插入"坑"中
function insertSort(A) {
for (var index= 1; index< A.length; index++) {
var x = A[index];
for (var j = index- 1; j >= 0 && A[j] > x; j--) {
A[j + 1] = A[j];
}
if (A[j + 1] != x) {
A[j + 1] = x;
println(A);
}
}
return A;
}
把字串切成陣列,用左右兩個指標向中間靠攏、邊走邊交換,最後再合併回字串。相比 split('').reverse().join('') 這種一行流,雙指標寫法更能看出「交換」這件事本質上發生了什麼。
//字符串反轉(比如:ABC -> CBA)
function inverse(s) {
var arr = s.split('');
var index= 0, j = arr.length - 1;
while (index< j) {
var t = arr[index];
arr[index] = arr[j];
arr[j] = t;
index++;
j--;
}
return arr.join('');
}
以上就是五個常見演算法的整理。把這些寫熟之後,再去看更進階的排序(快速排序、歸併排序)會順暢很多。