面試與日常開發中,這三個演算法出現的頻率最高。下面把實作與複雜度一起整理清楚。
前提條件是資料必須已排序。每次比對中間元素後砍掉一半搜尋範圍,因此平均時間複雜度為 O(log₂n)。
int halfFunction(int a[], int length, int number)
{
int start = 0;
int end = length - 1;
int index = 0;
while (start <= end)
{
index = start + (end - start) / 2;
if (a[index] == number)
{
return index;
}
else if (a[index] < number)
{
start = index + 1;
}
else
{
end = index - 1;
}
}
return -1; // 找不到時回傳 -1
}
兩個細節值得注意:中間值用 start + (end - start) / 2 而非 (start + end) / 2,可以避免整數溢位;迴圈條件用 start <= end,並在找不到時回傳 -1,語意比回傳最後一次的中間值清楚得多。
平均時間複雜度:O(n²)
空間複雜度:O(1),只用於元素交換
穩定性:穩定
void bubbleFunction(int a[], int length)
{
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
內層迴圈的 length - 1 - i 是關鍵:每一輪跑完,結尾都會多一個已排好的元素,不需要再比較。「穩定」的意思是數值相同的元素,排序後相對順序不會改變。
平均時間複雜度:O(n²)
空間複雜度:O(1)
穩定性:不穩定
void selectFunction(int a[], int length)
{
for (int i = 0; i < length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < length; j++)
{
if (a[j] < a[minIndex])
{
minIndex = j;
}
}
if (minIndex != i)
{
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
為什麼說它「不穩定」?以序列 [5, 5, 3] 為例,第一輪直接把索引 0 的 5 和索引 2 的 3 交換,原本在前面的那個 5 就被挪到後面去了,相同元素的相對順序因此被打亂。
另外提醒:標準的選擇排序應該是「每輪找最小值、跑完內層迴圈後只交換一次」。如果像某些範例那樣在內層迴圈裡每次都交換,雖然結果仍然正確,但交換次數會暴增,失去選擇排序本身的意義。