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

Question

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

Answer 2

您可以做的是分别从 (0) 和 (列表长度 - 1) 开始。

剧透（如果您不想要 JavaScript 中的解决方案，请不要阅读下面的代码或单击 link，而宁愿使用我在第一份声明中提供的信息）。

看看我在 JavaScript here 中的快速排序算法。

这里举个例子供以后参考：

function quicksort(items, left, right) {
    if (items.length > 1) {
        left = typeof left !== 'number' ? 0 : left;
        right = typeof right !== 'number' ? items.length - 1 : right;

        let index = partition(items, left, right);

        if (left < index - 1) {
            quicksort(items, left, index - 1);
        }

        if (index < right) {
            quicksort(items, index, right);
        }
    }

    return items;
}

function swap(items, firstIndex, secondIndex) {
    let temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function partition(items, left, right) {
    let pivot = items[Math.floor((right + left) / 2)],
        i = left,
        y = right;

    while (i <= y) {
        while(items[i] < pivot) {
            i++;
        }

        while(items[y] > pivot) {
            y--;
        }

        if (i <= y) {
            swap(items, i, y);
            i++;
            y--;
        }
    }

    return i;
}

let arr = [10, 3, 7, 5, 9, 2, 8, 1, 6, 4];

console.log(quicksort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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

I have trouble with quicksort algorithm

arrays

sorting

algorithm

quicksort