快速排序越界 (Kotlin)

Question

我正在尝试在 Kotlin 中实现快速排序。

我总是遇到越界错误，但我就是想不通为什么。

下面是我的代码：

fun quicksort(arr: MutableList<Int>) {
    quicksortHelper(arr, 0, arr.size + 1)
}

fun quicksortHelper(arr: MutableList<Int>, low: Int, high: Int) {
    if (low < high) {
        val partitionIdx = partition(arr, low, high)
        quicksortHelper(arr, low, partitionIdx)
        quicksortHelper(arr, partitionIdx + 1, high)
    }
}

fun partition (arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[low]
    var i= low
    var j = high
    while (i < j) {
        do {
            i++
        } while (arr[i] <= pivot)
        do {
            j--
        } while (arr[j] > pivot)
        if (i < j) {
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    val temp = arr[low]
    arr[low] = arr[j]
    arr[j] = temp

    return j
}

Answer 1

在 quicksort 中，您可能希望从高 arr.size - 1 开始。即：

fun quicksort(arr: MutableList<Int>) {
    quicksortHelper(arr, 0, arr.size - 1)
}

除此之外，您的数据透视方法似乎存在一些问题，索引中也存在一些不一致。您希望从 i = low - 1 和 j = high + 1 开始，否则您将跳过数组的第一个和最后一个元素。除了上述更改之外，将以下更改添加到您的 partition 函数应该可以解决您的问题：

fun partition (arr: MutableList<Int>, low: Int, high: Int): Int {
    val pivot = arr[(high + low) / 2] // pivot at the middle element instead of `low`
    var i = low - 1
    var j = high + 1
    while (i < j) {
        do {
            i++
        } while (arr[i] < pivot)
        do {
            j--
        } while (arr[j] > pivot)
        if (i < j) {
            val temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
    }
    val temp = arr[low]
    arr[low] = arr[j]
    arr[j] = temp

    return j
}

有关详细信息，请参阅 wikipedia quicksort page 上的 'Hoarse Partition Scheme' 伪代码。

快速排序越界 (Kotlin)

Quicksort out of bounds (Kotlin)

quicksort

kotlin