Java中的快速排序实现

Question

我写了这个快速排序的实现，作为我自己的一点实践和回顾。我没有把我的算法建立在我自己对快速排序的理解之上，并且在纸上通过了几个例子，所以请让我知道我可以做的任何改进或优化！

import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;

/**
 * A simple, generic, in-place implementation of quicksort
 * @implNote The pivot used during the partitioning step is selected at random
 */
public class Quicksort {

    /**
     * Sort the given array using quicksort
     * @param arr Array to sort
     * @param <E> Type of the elements contained by arr
     */
    public static <E extends Comparable> void sort(ArrayList<E> arr) {
        sort(0, arr.size() - 1, arr);
    }

    /**
     * Sorts a designated section of the given array using quicksort
     * @param left  Lower-bound index of section (inclusive)
     * @param right Upper-bound index of section (inclusive)
     * @param arr   Array to perform sort within
     * @param <E>   Type of the elements contained by arr
     */
    private static <E extends Comparable> void sort(int left, int right, ArrayList<E> arr) {
        // Exit if section contains only a single element, or is invalid
        if (right - left < 1) {
            return;
        }

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

        // Partition this section of the array
        int pivotFinalIndex = partition(left, right, pivot, arr);

        // Sort the two new partitions
        sort(left, pivotFinalIndex - 1, arr);
        sort(pivotFinalIndex + 1, right, arr);
    }

    /**
     * Partition a section of an array around a pivot value
     * @param left  Lower-bound index of section (inclusive)
     * @param right Upper-bound index of section (inclusive)
     * @param pivot Index of the value to partition around
     * @param arr   Array to perform partitioning within
     * @param <E>   Type of the elements contained by arr
     * @return      The final index of the partition value
     */
    private static <E extends Comparable> int partition(int left, int right, int pivot, ArrayList<E> arr) {
        // Move pivot to left-most position (get out of the way)
        Collections.swap(arr, left, pivot);
        pivot = left;

        // Perform partitioning
        int rightPartitionStart = left + 1;
        for (int i = left + 1; i <= right; i++) {
            // If our current value is less than our pivot, move it into the left partition
            if (arr.get(i).compareTo(arr.get(pivot)) < 0) {
                Collections.swap(arr, i, rightPartitionStart);
                rightPartitionStart++;
            }
        }

        // Put pivot back where it belongs (in between partitions)
        Collections.swap(arr, pivot, rightPartitionStart - 1);
        pivot = rightPartitionStart - 1;

        return pivot;
    }
}

Answer 1

1

我会宣布<E extends Comparable> void sort(ArrayList<E> arr)为<E extends Comparable<? super E>> void sort(ArrayList<E> arr)

2

void sort(int left, int right, ArrayList<E> arr) {
    ...
}

我建议您将其设置为public，并将这些论点重新组织如下：

void sort(ArrayList<E> arr, int fromIndex, int toIndex)

在您的版本中，fromIndex对应于left，而toIndex对应于right + 1：这是JDK排序算法中的约定，因此toIndex是唯一的上限。

3

我会制作三参数版本的public，因为有时人们只想对数组的子范围进行排序(在我们的例子中是ArrayList )。

4

将构造函数声明为私有：

private Quicksort() {}

希望这能帮上忙。