有了昨天的介紹後，我們今天來介紹它們的演算法！

Counting Sort

Counting Sort 是一種用於排序一組數字的演算法，它主要適用於範圍較小的非負整數。

這個演算法的主要思想是建立一個稱為「計數陣列」的輔助數組，該陣列的索引代表待排序數組中的數字，而其值則代表這個數字在待排序數組中出現的次數。

通過統計每個數字的出現次數，我們可以根據這些次數重新構建已排序的數組。

演算法

1. 初始化一個計數陣列，其大小等於待排序數組中最大元素的值加一。（這個計數陣列用來記錄每個元素的出現次數）
2. 遍歷待排序數組，對於每個元素，將計數陣列中相應索引位置的計數值加1。
3. 累加計數陣列中的值，這將告訴我們每個元素在排序後的數組中的位置。
4. 建立一個與待排序數組相同大小的輔助數組，稱為排序結果數組。
5. 再次遍歷待排序數組，對於每個元素，從計數陣列中找到它在排序結果數組中的位置，將它放在那個位置。
6. 完成後，排序結果數組即為已排序的數組。

它的優點是它在時間複雜度上可以達到，其中是待排序數組的大小，是待排序數組中最大元素的值。

然而，它只適用於非負整數，且當相對較大時，可能需要大量的記憶體空間。

因此，計數排序在某些特定情況下非常有效，但不適用於一般情況下的排序。

// Counting sort
class CountingSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        val output = IntArray(n)
        val count = IntArray(256)
        for (i in 0..255) count[i] = 0
        for (i in 0 until n) ++count[arr[i]]
        for (i in 1..255) count[i] += count[i - 1]
        for (i in n - 1 downTo 0) {
            output[count[arr[i]] - 1] = arr[i]
            --count[arr[i]]
        }
        for (i in 0 until n) arr[i] = output[i]
    }

    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(5, 0, 1, 88, 9, 112, 58)
    val n = arr.size
    val ob = CountingSort()
    ob.sort(arr)
    println("sorted array")
    ob.printArray(arr, n)
}

Radix Sort

Radix Sort 是一種整數排序演算法，它的主要思想是將整數按照位數進行排序，從最低位（個位）到最高位（最高位），逐步排列整個數列，直到整個數列有序。

這個演算法的名稱中的"基數"指的是數字的進位制，通常是以十進位為例。

Radix Sort 首先根據個位數（最低位）的大小將整數分成多個桶（bucket），每個桶中包含具有相同個位數的整數。

然後，它依次處理每個桶，對桶中的數字按照十位數進行排序，再依次按百位、千位等等進行排序，直到排序完成。最終，所有的桶都按照每一位數排列，整個數列也就變成了有序的。

Radix Sort 的效率取決於整數的位數，當位數較少時，它可以非常高效地排序整數。

然而，對於位數較多的整數，它的效率可能會下降。

優點是它是一種穩定的排序算法，並且不需要比較元素的大小，因此對於某些特定情況下，它可能比其他排序算法更快。

Radix Sort 是一種通過按位數進行多次排序來實現整數排序的演算法，它的效率和性能取決於整數位數的多少。

// Radix sort
class RadixSort {
    fun sort(arr: IntArray) {
        val n = arr.size
        val m = getMax(arr, n)
        for (exp in 1..m) countSort(arr, n, exp)
    }

    fun getMax(arr: IntArray, n: Int): Int {
        var mx = arr[0]
        for (i in 1 until n) if (arr[i] > mx) mx = arr[i]
        return mx
    }

    fun countSort(arr: IntArray, n: Int, exp: Int) {
        val output = IntArray(n)
        val count = IntArray(10)
        for (i in 0..9) count[i] = 0 // Initialize count array, count[i] will store total count of digit i in input array, range 0 to 9
        for (i in 0 until n) ++count[arr[i] / exp % 10]
        for (i in 1..9) count[i] += count[i - 1]
        for (i in n - 1 downTo 0) {
            output[count[arr[i] / exp % 10] - 1] = arr[i]
            --count[arr[i] / exp % 10]
        }
        for (i in 0 until n) arr[i] = output[i]
    }

    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(5, 0, 1, 88, 9, 112, 58)
    val n = arr.size
    val ob = RadixSort()
    ob.sort(arr)
    println("sorted array")
    ob.printArray(arr, n)
}

Bucket Sort

Bucket Sort 是一種排序算法，它的主要思想是將一個待排序的數據集分成多個稱為"桶"的容器，然後分別對每個桶內的元素進行排序，最終將這些有序的桶按照一定的順序合併起來，得到整個數據集的有序結果。

具體步驟如下：

1. 建立一個固定數量的空桶，每個桶代表一個範圍或區間。
2. 將待排序的元素按照其值的大小分配到不同的桶中。這可以通過一個映射函數將元素的值轉換為桶的索引來實現。
3. 對每個非空的桶內的元素進行排序。這可以使用任何排序算法，通常選擇快速排序、插入排序等。
4. 按照桶的順序，將每個桶內的元素依次合併起來，形成最終的排序結果。

優點是可以在某些情況下具有較高的效率，特別是當待排序數據集在某個範圍內分佈較為均勻時。

然而，它也有一些限制，例如需要事先知道待排序數據的範圍，且對於數據分佈不均勻的情況，可能需要調整桶的數量和範圍，以達到較好的效果。

fun insertionSort(arr: ArrayList<Int>) {
    val n = arr.size
    for (j in 1 until n) {
        val key = arr[j]
        var i = j - 1
        while (i >= 0 && arr[i] > key) {
            arr[i + 1] = arr[i]
            i--
        }
        arr[i + 1] = key
    }
}

fun bucketSort(arr: Array<Int>) {
    val n = arr.size
    var maxVal = Int.MIN_VALUE
    var minVal = Int.MAX_VALUE

    for (i in 0 until n) {
        if (arr[i] > maxVal) {
            maxVal = arr[i]
        }
        if (arr[i] < minVal) {
            minVal = arr[i]
        }
    }

    val bucketCount = maxVal - minVal + 1
    val buckets = Array(bucketCount) { ArrayList<Int>() }

    for (i in 0 until n) {
        val index = arr[i] - minVal
        buckets[index].add(arr[i])
    }

    var index = 0
    for (bucket in buckets) {
        if (bucket.isNotEmpty()) {
            insertionSort(bucket)
            for (num in bucket) {
                arr[index] = num
                index++
            }
        }
    }
}

fun main(args: Array<String>) {
    val A = arrayOf(12, 0, 34, 64, 90, 12)
    println("Before sorting:")
    for (i in A) {
        print("$i ")
    }
    println()
    bucketSort(A)
    println("\nAfter sorting:")
    for (i in A) {
        print("$i ")
    }
}

所有 Code 可以在 Github 找到 ～

明天進入到 Tree 的環節！

Reference

• Program for Bucket Sort in Kotlin