algorithm - 快速排序分区程序(Lomuto)中的交换条件？

Question

我已经实现了算法简介一书中的快速排序。书上规定的程序如下

但是我在第 4 行没有看到小于等于比较的要求，不应该仅仅小于比较就足够了。

为了检查我是否编写了以下程序，它是否在我测试过的数据集上正常工作。

private fun partition(start: Int, end: Int, arr: Array<Int>) : Int{
        var pivotIndex = end
        var maximumElementIndex = start
        for(index in start until end){
            if(arr[index]<arr[pivotIndex]){
                val temp = arr[index]
                arr[index] = arr[maximumElementIndex]
                arr[maximumElementIndex] = temp
                maximumElementIndex++
            }
        }

        val temp = arr[maximumElementIndex]
        arr[maximumElementIndex] = arr[pivotIndex]
        arr[pivotIndex] = temp
        return maximumElementIndex
    }

我已经根据以下输入对其进行了测试

• 所有元素相等的数组
• 排序数组
• 倒序排列
• 多个随机数据集

所以我在这里缺少什么？

Answer 1

除了使用 <= 之外，还有更多差异.它还在初始化 i = p-1; , 最后的交换是 swap(A[i+1], A[r]); .它只是 Lomuto 分区方案的一种变体。您的示例代码与 Wiki 文章中的代码相匹配:

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

请注意，这两种方案都是已排序数据、反向排序数据和所有相等元素的最坏情况，因为分区只会在每个递归级别将分区大小减少 1。使用中间值作为基准并将其交换到末尾可以解决排序或反向排序数据的问题，但 Lomuto 通常会随着相等元素数量的增加而变得更糟。

Hoare 方案，使用中间元素，通常随着重复次数的增加而变得更好。存在不必要的等于枢轴值的元素交换，但随着重复项数量的增加，分区接近了均匀大小拆分的理想情况，而缓存有助于进行不必要的交换。

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme