快速排序算法未正确分配数据透视 [英] Quicksort Algorithm not assigning pivot correctly

问题描述

我观看了这种快速排序算法的出色可视化效果: http://www.youtube.com/watch?v = Z5nSXTnD1I4

I watched this fantastic visualization of a quick sort algorithm: http://www.youtube.com/watch?v=Z5nSXTnD1I4

我觉得我真的很了解快速排序的原理，并借助一些在线指南，着手创建自己的快速排序.
这是我想出的:

I felt I really understood the principles behind quick sort and, with the help of some guides online, set about creating my own quick sort.
This is what I came up with:

public void quickSort(int[] a, int left, int right) {

    int index = partition(a, left, right);
    if (left < index - 1)
      quickSort(a, left, index);
    if (index < right)
      quickSort(a, index + 1, right);
}

private int partition (int[] a, int left, int right) {
    int i = left - 1;
    int j = right + 1;
    int pivot = a[0];

    while (i < j) {

        i++;

        while (a[i] < pivot)
            i++;

        j--;

        while (a[j] > pivot)
            j--;

        if (i < j)
            swap (a, i, j);
    }
return i;
}   

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

left和right的值如下:

The values of left and right are the following:

left = 0
right = array size - 1

不幸的是，输出不正确.问题似乎出在我对枢轴的处理上.在我观察的可视化中，讲师物理地移开了枢轴，使指针指向无处.他继续进行本教程，直到到达i和j(我分别称为左右)都指向同一个空白点的位置时，他插入了枢轴并继续.

Unfortunately the output isn't correct. The problem appears to lie in my treatment of the pivot. In the visualization I watched, the instructor physically removed the pivot and left the pointer pointing at nothing. He carried on with the tutorial and when he got to the point where i and j (what I call left and right) both pointed at the same empty spot, he inserted the pivot and carried on.

由于我实际上将枢轴固定在适当的位置，因此很难正确地对其进行排序.

As I am physically keeping the pivot in place, I am finding it difficult to properly sort it.

在这段代码中，我正在处理输入:

In this code, I am working with the input:

4 8 1 6 3 7 2 5

我得到输出:

1 3 2 6 8 7 4 5

一旦在算法的开始就对"4"值(即枢轴)进行排序，我就不会再使用它，这会使所有内容一目了然.另外，我认为quickSort方法存在问题.

Once the "4" value (i.e. the pivot) is sorted at the very start of the algorithm, I never resort it, which throws everything off. Additionally, I think there is something wrong with the quickSort method.

有人可以给我一些建议吗?谢谢.

Could someone give me a few pointers? Thanks.

此处的两个编辑已删除，因为其中包含不必要和不正确的信息.其中之一将枢轴更改为:(左+右)/2.这当然是错误的，原因如下文所述.

推荐答案

我不得不删除分区，因为您同时需要i和j.看起来应该像这样:

I had to get rid of partition, because you need both i and j. It should look like this:

public void quickSort(int[] a, int left, int right) {

    int i = left; // Was -1 
    int j = right; // Was +1
    int pivot = a[left + (right - left) / 2]; // Pivot is the value of the middle index, not the index itself
    while (i <= j) { // Changed terminating condition
        //   i++;  Not needed
        while (a[i] < pivot) { 
            i++;
        }
        //    j++; Not needed
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {  // Changed terminating condition
            swap(a, i, j);
            i++;  // You need to progress the indexes after the swap
            j--;
        }
    }

    System.out.println(Arrays.toString(a));
    if (left < j) {  // Changed condition
        quickSort(a, left, j);
    }
    if (i < right) { 
        quickSort(a, i, right); // was i + 1
    }
}

输出:

[4, 5, 1, 2, 3, 7, 6, 8]
[1, 5, 4, 2, 3, 7, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

这篇关于快速排序算法未正确分配数据透视的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！