基礎排序：O(n²) 排序演算法#

基礎排序演算法時間複雜度為 O(n²)，適用於小規模資料。雖然效率不高，但實作簡單，是學習排序的起點。

為什麼要排序？#

排序的價值不在排序本身，而在於「讓未來的搜尋變便宜」——它其實是一種對未來查詢的預防性投資。判準很簡單：一筆資料若會被反覆搜尋，且預先排序的成本低於每次線性掃描的累積成本，才值得排；只查一次的東西，排序純粹是浪費。

換句話說：排序一個你永遠不會搜尋的東西是徹底浪費；搜尋一個你從未排序的東西，只是稍微低效。 一旦資料有序，二分查找就讓 O(log n) 的查詢成為可能，這正是排序前置成本要換回的東西。

不要只盯著排序這一次的開銷：排序的成本會攤提到未來每一次查詢上。查得越多次，當初那一次排序就越划算。

核心概念#

有序度與逆序度#

  • 有序度：陣列中有序元素對的數量，滿足 a[i] <= a[j] 且 i < j
  • 滿有序度：完全有序時的有序度 = n*(n-1)/2
  • 逆序度 = 滿有序度 - 有序度

排序的本質就是增加有序度、減少逆序度，直到達到滿有序度。

冒泡排序 (Bubble Sort)#

每次比較相鄰元素，將較大者「冒泡」到右側。

特性說明
時間複雜度最好 O(n)、最壞/平均 O(n²)
空間複雜度O(1)，原地排序
穩定性穩定
冒泡排序程式碼
fun bubbleSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n) {
        var swapped = false
        for (j in 0 until n - i - 1) {
            if (arr[j] > arr[j + 1]) {
                val tmp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = tmp
                swapped = true
            }
        }
        if (!swapped) break  // 優化：無交換代表已有序
    }
    return arr
}

插入排序 (Insertion Sort)#

將陣列分為「已排序區」與「未排序區」，逐一將未排序元素插入正確位置。

特性說明
時間複雜度最好 O(n)、最壞/平均 O(n²)
空間複雜度O(1)，原地排序
穩定性穩定
插入排序程式碼
fun insertionSort(arr: IntArray): IntArray {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
    return arr
}

為何插入排序優於冒泡排序？

兩者時間複雜度相同，但冒泡的「交換」需要 3 次賦值，插入的「移動」只需 1 次。實測顯示，插入排序比冒泡排序快約 3-7 倍。

選擇排序 (Selection Sort)#

每次從未排序區選出最小元素，放到已排序區末尾。

特性說明
時間複雜度最好/最壞/平均皆為 O(n²)
空間複雜度O(1)，原地排序
穩定性不穩定
選擇排序程式碼
fun selectionSort(arr: IntArray): IntArray {
    val n = arr.size
    for (i in 0 until n) {
        var minIdx = i
        for (j in i + 1 until n) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j
            }
        }
        val tmp = arr[i]
        arr[i] = arr[minIdx]
        arr[minIdx] = tmp
    }
    return arr
}

選擇排序是不穩定的！例如 [5, 8, 5, 2, 9]，第一次選擇最小值 2 與第一個 5 交換後，兩個 5 的相對順序改變了。

三種基礎排序比較#

演算法最好最壞/平均空間穩定性一句話
冒泡排序O(n)O(n²)O(1)穩定交換成本高，實務幾乎不用
插入排序O(n)O(n²)O(1)穩定近乎有序時最快，小區間首選
選擇排序O(n²)O(n²)O(1)不穩定交換次數最少，但無法提早結束

實務應用建議#

  1. 小規模資料：插入排序是首選
  2. 幾乎有序的資料：插入排序效率接近 O(n)
  3. 工業級排序函式：當區間元素 <= 4 時，通常切換為插入排序
Backward 排序演算法 進階排序 Forward