是否可以使用列表在 loco 中实现快速排序？

Question

我在 java 中使用数组以静态方式实现了快速排序算法。

public static <T extends Comparable<T>> void quickSort(T[] A){
    quickSort(A, 0, A.length-1);
}

private static <T extends Comparable<T>> void quickSort(T[] A, int p, int r){
    if(p < r){
        int q = partition(A, p, r);
        quickSort(A, p, q);
        quickSort(A, q+1, r);
    }
}

private static <T extends Comparable<T>> int partition(T[] A, int p, int r){
    T x = A[p];
    int i = p;
    int j = r;
    while(true){
        while(A[j].compareTo(x) > 0 && j > p){
            j--;
        }
        while(A[i].compareTo(x) < 0 && i < r){
            i++;
        }
        if(i < j)
            swap(A, i, j);
        else
            return j;
    }
}

有没有办法使用列表实现此算法，保留 "in loco" 属性。我认为使用没有索引的列表是一个问题，因为您需要知道在两个不同的 "while" 之后，如果引用属于另一个节点之前的节点。有谁知道避免这种麻烦的方法吗？

Answer 1

使用列表而不是数组实现相同的算法没有问题。您可以像使用数组一样使用 List：使用 set 和 get 方法。它还具有方便的方法，例如 subList 对快速排序很有用。子列表是列表的视图；不涉及复制。所以这样就不需要通过上下限了。

static void sort(List<Integer> list) {
    if (!list.isEmpty()) {
        int pivotValue = list.get(list.size() - 1);
        int storeIndex = 0;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) < pivotValue) {
                Collections.swap(list, i, storeIndex++);
            }
        }
        Collections.swap(list, list.size() - 1, storeIndex);
        sort(list.subList(0, storeIndex));
        sort(list.subList(storeIndex + 1, list.size()));
    }
}

您提到了使用不带索引的列表的问题。当然，可以在不使用索引的情况下从列表中 add 和 remove 对象。然而，很难看出如何在不使用索引的情况下实现快速排序。例如选择枢轴和交换元素都需要索引。

是否可以使用列表在 loco 中实现快速排序？

is it possible to implement quicksort in loco with a list?

java

list

quicksort