arrays - 我在使用快速排序算法时遇到问题

Question

我对快速排序算法有疑问。我在互联网上的不同页面以及维基百科上阅读过有关它的信息。但他们并没有详细解释太多。当您选择最后一个元素作为枢轴元素时，我已经理解了他们的示例。在这种情况下，您选择另外两个变量 i, j，其中 i 将遍历数组，直到找到一个大于 pivotelement 和 j 的元素> 直到找到一个低于枢轴元素的元素。找到了，我们切换i,j显示的元素，继续...

我的问题是，你首先选择哪个元素作为i,j？假设我们给定了这个数组并且枢轴元素是 1:

9 1 4 2 0 7

我的i是什么，我的j是什么？

我认为第一个元素是i，所以9 j 是数组中的最后一个元素，所以 7?

Answer 1

维基百科解释得相当好:

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion

所以答案是肯定的，将i设置为数组的第一个元素，将j设置为数组的最后一个元素并移动它们直到它们相遇，这是基本的快速排序算法的分区部分。

每当您不确定时，最好检查一下确切的代码。有多种变体，您可以找到一个，例如here :

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

如您所见，left 和right(相当于您的i 和j)设置为数组的第一个和最后一个索引。