Quicksort 实现：使用随机枢轴时几乎已排序

Question

我正在努力实现快速排序，作为我自己的一些练习和复习。目前这只是原始整数数组的简单实现。得到这个工作正常后，我打算使它通用。

我下面的内容仍然有一个小错误，我无法找到。我最初写它是为了简单地使用左索引作为基准，一切正常。然而，一旦我完成编写并将其切换为使用随机枢轴，事情就不再完全正确了。我的测试数组几乎已排序，但仍有一些元素距离它们应有的位置有两到三个索引。

以下是我的一些测试用例，这些用例在运行时展示了不正确的行为：

6, 5, 1, 3, 8, 4, 7, 9, 2

1, 2, 3, 4, 5

5, 4, 3, 2, 1

 /**
 * Sort an integer array using quicksort
 * 
 * @param a Array to sort
 */
public static void quicksort(int[] a) {
    partition(0, a.length - 1, a);
}

/**
 * Partition a section of an integer array around a randomly selected pivot within that section
 *
 * @param left Lower-bound index of section (inclusive)
 * @param right Upper-bound index of section (inclusive)
 * @param a Array to perform partitioning within
 */
private static void partition(int left, int right, int[] a) {
    // Exit if partition is only a single element
    if (right - left < 1) { return; }

    // Select a pivot at random
    int pivot = ThreadLocalRandom.current().nextInt(left, right + 1);

    // Move pivot to left-most position (get out of the way)
    swap(left, pivot, a);

    // Perform partitioning
    int cur = left + 1;
    for (int i = left + 1; i <= right; i++) {
        if (a[i] < a[pivot]) {
            swap(i, cur, a);
            cur++;
        }
    }

    // Put pivot back where it belongs
    swap(left, cur - 1, a);

    // Partition the two new partitions
    partition(left, cur - 2, a);
    partition(cur, right, a);
}

/**
 * Swaps two elements in an array of integers
 *
 * @param i Index of first element to swap
 * @param j Index of second element to swap
 * @param a Integer array to perform swap on
 */
private static void swap(int i, int j, int[] a) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Answer 1

好的，尝试使用左而不是枢轴。它将反转列表的排序。

if (a[i] > a[left]) {
            swap(i, cur, a);
            cur++;
}

您没有考虑更改。

我更习惯于向右旋转。我让你的实现很小。我的问题是，第一个右边必须 > 左边，并且可能需要快速排序分区 (left,cur-1,a)。

交换的位置也应该已经排序。尽管您以正确的基础方法来考虑这一点。

partition(left, cur -1 , a);
partition(cur + 1, right, a);

您可以在 Wikipedia

阅读有关实施的信息

我的代码在编码场运行。

public class HelloWorld{

   int[] a = null;



    /**
 * Sort an integer array using quicksort
 * 
 * @param a Array to sort
 */
public void quicksort() {
    partition(0, a.length - 1, a);
}

/**
 * Partition a section of an integer array around a randomly selected pivot within that section
 *
 * @param left Lower-bound index of section (inclusive)
 * @param right Upper-bound index of section (inclusive)
 * @param a Array to perform partitioning within
 */
private  void partition(int left, int right, int[] a) {
    // Exit if partition is only a single element
    if (right <= left || right - left == 0) { return; }

    // Select a pivot at random
    int pivot =  left + new java.util.Random().nextInt(right - left);
    pivot = right;

    // Move pivot to left-most position (get out of the way)
    swap(right, pivot, a);

    // Perform partitioning
    int cur = left;
    for (int i = left; i < right; i++) {
        if (a[i] <= a[right]) {
            swap(i, cur, a);
            cur++;
        }
    }

    // Put pivot back where it belongs
    swap(cur, right , a);

    // Partition the two new partitions
    partition(left, cur -1 , a);
    partition(cur + 1, right, a);
}

/**
 * Swaps two elements in an array of integers
 *
 * @param i Index of first element to swap
 * @param j Index of second element to swap
 * @param a Integer array to perform swap on
 */
private void swap(int i, int j, int[] a) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


     public static void main(String []args){
         int[] arr = new int[]{0,4,2,3,9,11,20,100,50,32,45,27,13,2,1,4,99,1,4};
         HelloWorld hw = new HelloWorld();
         hw.a = arr;
         hw.quicksort();
         for(int i = 0;i< arr.length;i++){
             System.out.println(arr[i]);
         }
     }
}

这里是枢轴在左边的代码。

public class HelloWorld{

   int[] a = null;



    /**
 * Sort an integer array using quicksort
 * 
 * @param a Array to sort
 */
public void quicksort() {
    partition(0, a.length - 1, a);
}

/**
 * Partition a section of an integer array around a randomly selected pivot within that section
 *
 * @param left Lower-bound index of section (inclusive)
 * @param right Upper-bound index of section (inclusive)
 * @param a Array to perform partitioning within
 */
private  void partition(int left, int right, int[] a) {
    // Exit if partition is only a single element
    if (right <= left || right - left == 0) { return; }

    // Select a pivot at random
    int pivot =  left + new java.util.Random().nextInt(right - left);


    // Move pivot to left-most position (get out of the way)
    swap(left, pivot, a);

    // Perform partitioning
    int cur = left + 1;
    for (int i = left +1 ; i <=  right; i++) {
        if (a[i] < a[left]) {
            swap(i, cur, a);
            cur++;
        }
    }


    // Put pivot back where it belongs
    swap(cur - 1 , left , a);

    // Partition the two new partitions
    partition(left, cur - 2 , a);
    partition(cur , right, a);
}

/**
 * Swaps two elements in an array of integers
 *
 * @param i Index of first element to swap
 * @param j Index of second element to swap
 * @param a Integer array to perform swap on
 */
private void swap(int i, int j, int[] a) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


     public static void main(String []args){
         int[] arr = new int[]{6, 5, 1, 3, 8, 4, 7, 9, 2};
         HelloWorld hw = new HelloWorld();
         hw.a = arr;
         hw.quicksort();
         for(int i = 0;i< arr.length;i++){
             System.out.println(arr[i]);
         }
     }
}

Answer 2

正在将我的评论转化为答案：

在这部分代码中，您将枢轴元素与最左边的元素交换：

// Select a pivot at random
int pivot = ThreadLocalRandom.current().nextInt(left, right + 1);

// Move pivot to left-most position (get out of the way)
swap(left, pivot, a);

但是，您实际上并没有更改数据透视元素的索引。这意味着在此分区逻辑中，您正在查看数组中的错误索引：

for (int i = left + 1; i <= right; i++) {
    if (a[i] < a[pivot]) {
        swap(i, cur, a);
        cur++;
    }
}

Quicksort 实现：使用随机枢轴时几乎已排序

Quicksort implementation: nearly sorted when using random pivot

java

arrays

sorting

quicksort