今天我想來點 CLRS

我們會透過 Introduction to Algorithms 來講解 Quick Sort 和 Heap Sort

Quick Sort

Quick Sort 是一種常見的排序演算法，而且在實踐中通常具有優秀的效能。

它屬於比較排序的一種，通過比較元素的大小來進行排序。

選擇一個參考元素（通常稱為「樞紐」或「基準」），英文稱 pivot，然後將所有比參考元素小的元素移到其左側，將所有比參考元素大的元素移到其右側。

然後，分別對左右兩側的子數列進行遞歸排序，直到整個數列有序。

以下是快速排序的簡要步驟：

1. 選擇一個參考元素（基準），可以是數列中的任何一個元素。
2. 分割：將數列劃分為兩個子數列，一個包含所有比參考元素小的元素，另一個包含所有比參考元素大的元素。這一步又稱為分區（partition）。
3. 遞歸排序：對左側子數列和右側子數列分別應用快速排序，重複以上步驟。
4. 合併：無需合併步驟，因為每個子數列都已經排序完畢。整個數列就自然地變得有序。

快速排序的關鍵在於適當地選擇參考元素和高效的分割過程，以確保排序的效率。在平均情況下，快速排序的時間複雜度為，其中是要排序的元素數量。

但最壞情況下，時間複雜度可能達到，這種情況通常可以通過選擇良好的參考元素來避免。

// Quick sort algorithm 
class QuickSort {
    fun sort(arr: IntArray, low: Int, high: Int) {
        if (low < high) {
            val pi = partition(arr, low, high)
            sort(arr, low, pi - 1)
            sort(arr, pi + 1, high)
        }
    }

    fun partition(arr: IntArray, low: Int, high: Int): Int {
        val pivot = arr[high]
        var i = low - 1
        for (j in low until high) {
            if (arr[j] < pivot) {
                i++
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
        val temp = arr[i + 1]
        arr[i + 1] = arr[high]
        arr[high] = temp
        return i + 1
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(-8, -8, -87, 12, 0, 34, 64, 90, 12)
    val quickSort = QuickSort()
    quickSort.sort(arr, 0, arr.size - 1)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

Randomized Quick sort

Randomized Quick Sort 是將一個未排序的數列分成兩個子數列，然後分別對這兩個子數列進行排序，最終達到整個數列有序的目的。

1. 選擇一個輸入數列中的元素作為基準元素（pivot）。這個選擇通常是隨機的，以確保算法的平均性能。
2. 將數列中的元素分為兩部分：小於基準元素的元素和大於基準元素的元素。
3. 遞歸地對這兩部分子數列進行快速排序。也就是說，對於小於基準元素的子數列和大於基準元素的子數列，分別重複步驟1和步驟2，直到每個子數列只包含一個元素，即已經排序完成。
4. 最終，將所有子數列合併在一起，即可獲得一個完全有序的數列。

隨機快速排序的主要優勢在於其平均時間複雜度為，其中是待排序數列的元素數量。然而，在最壞情況下，時間複雜度為，但這種情況相對較少出現，因為基準元素的隨機選擇降低了最壞情況的機率。

// Randomized Quick sort
class RandomizedQuickSort {
    // This Function helps in calculating
    // random numbers between low(inclusive)
    // and high(inclusive)
    fun randPartition(arr: IntArray, low: Int, high: Int): Int {
        val n = high - low + 1
        val pivot = (Math.random() % n).toInt()
        swap(arr, low + pivot, high)
        return partition(arr, low, high)
    }

    fun partition(arr: IntArray, low: Int, high: Int): Int {
        val pivot = arr[high]
        var i = low - 1
        for (j in low until high) {
            if (arr[j] <= pivot) {
                i++
                swap(arr, i, j)
            }
        }
        swap(arr, i + 1, high)
        return i + 1
    }

    fun swap(arr: IntArray, i: Int, j: Int) {
        val temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }

    fun quickSort(arr: IntArray, low: Int, high: Int) {
        if (low < high) {
            val pi = randPartition(arr, low, high)
            quickSort(arr, low, pi - 1)
            quickSort(arr, pi + 1, high)
        }
    }

    fun printArray(arr: IntArray, size: Int) {
        for (i in 0 until size) print(arr[i].toString() + " ")
        println()
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(-88, 58, -9, 112, 5, 0, 1)
    val n = arr.size
    val ob = RandomizedQuickSort()
    ob.quickSort(arr, 0, n - 1)
    println("sorted array")
    ob.printArray(arr, n)
}

Heap Sort

Heap Sort 屬於比較排序的一種。

它通過建立和維護一個二叉堆（通常是一個 Max heap 或 Min heap）來完成排序操作。

Max heap 中的每個節點都比其子節點大，而 Min heap 中的每個節點都比其子節點小。

Heap Sort 分為兩個主要步驟：

• 建立堆 (Heapify)
• 不斷從堆中取出根節點 (Build Heap)

Heapify

首先，將待排序的數據視為一個完全二叉樹，並從最後一個非葉子節點開始，依次對每個節點進行調整，使得整棵樹滿足堆的性質。

如果希望升序排序，則建立最大堆，如果希望降序排序，則建立最小堆。

Build Heap

堆的根節點是擁有最大（或最小，根據排序順序）值的節點。

將根節點取出並放入已排序的部分，然後重新調整剩餘的堆，以確保其仍然滿足堆的性質。

重複這個步驟，直到堆中只剩下一個元素。

當堆中只剩下一個元素時，排序完成，所有元素都已按升序或降序排列。

堆排序的優點是它具有固定的時間複雜度，無論輸入數據如何，都具有的時間複雜度，其中是要排序的元素數量。然而，它可能需要更多的記憶體，因為需要維護整個堆結構。

Heap Sort 特別適合處理大量數據。

// Heap sort
class HeapSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        for (i in n / 2 - 1 downTo 0) {
            heapify(arr, n, i)
        }
        for (i in n - 1 downTo 0) {
            val temp = arr[0]
            arr[0] = arr[i]
            arr[i] = temp
            heapify(arr, i, 0)
        }
    }

    fun heapify(arr: IntArray, n: Int, i: Int) {
        var largest = i
        val l = 2 * i + 1
        val r = 2 * i + 2
        if (l < n && arr[l] > arr[largest]) {
            largest = l
        }
        if (r < n && arr[r] > arr[largest]) {
            largest = r
        }
        if (largest != i) {
            val swap = arr[i]
            arr[i] = arr[largest]
            arr[largest] = swap
            heapify(arr, n, largest)
        }
    }
}

// main function
fun main(args: Array<String>) {
    val arr = intArrayOf(-8, -8, -87, 12, 0, 34, 64, 90, 12)
    val heapSort = HeapSort()
    heapSort.sort(arr)
    println("Sorted array")
    for (i in arr.indices) {
        print(arr[i].toString() + " ")
    }
}

所有 Code 可以在 Github 找到 ～

Reference

• Introduction to Algorithms - MIT Press