Kotlin 快速排序算法实现详解及示例

以下是 Kotlin 中的快速排序算法的实现：

fun quickSort(arr: IntArray, left: Int, right: Int) {
    if (left < right) {
        val pivotIndex = partition(arr, left, right)
        quickSort(arr, left, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, right)
    }
}

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

该实现使用递归来实现快速排序。在每一次递归中，通过 partition 函数将数组分为两个子数组，其中左边子数组的所有元素都小于右边子数组的所有元素。然后递归地对两个子数组进行排序，直到整个数组有序。

在 partition 函数中，选择数组中最后一个元素作为枢轴（pivot）。然后从左到右遍历数组，将小于枢轴的元素交换到左边，大于等于枢轴的元素交换到右边。最后，将枢轴交换到合适的位置（i+1），并返回枢轴的位置。

要排序一个整数数组，可以调用 quickSort 函数并传入数组的左右边界：

val arr = intArrayOf(5, 2, 9, 1, 5, 6)
quickSort(arr, 0, arr.size - 1)
println(arr.contentToString()) // [1, 2, 5, 5, 6, 9]