java - java中的快速排序列表

Question

我正在尝试使用 java 练习快速排序列表，我认为这是正确的，但它显示“主线程中的异常...”

public class QuickSort {

  public static void sort(List<Integer> list) {
    sort(list, 0, list.size() - 1);
  }

  public static void sort(List<Integer> list, int from, int to) {
    if (list.size() <= 1) {
        return;
    }
    int pivot = from;
    int left = from + 1;
    int right = to;
    while (left < right) {
        while (list.get(pivot) >= list.get(left)) {
            left++;
        }
        while (list.get(pivot) <= list.get(right)) {
            right--;
        }
        if (left < right) {
            Collections.swap(list, left, right);
        }
    }
    Collections.swap(list, pivot, left - 1);
    sort(list, from, pivot - 1);
    sort(list, pivot + 1, to);
  }
}

Answer 1

你的问题在这里:

while (list.get(pivot) <= list.get(right)) {
        right--;
    }

因为，在最坏的情况下，比如一个已经排序的 list，您的 right-- 将是负数。

看看下面的代码，这会给你一个想法:

public static void quicksort(List<Integer> list, int left, int right) {
    int q;
    if (right > left) {
        q = partition(list, left, right);
        // after ‘partition’
        // list[left..q-1] ≤ list[q] ≤ list[q+1..right]
        quicksort(list, left, q - 1);
        quicksort(list, q + 1, right);
    }
}

static int partition(List<Integer> list, int left, int right) {
    int P = list.get(left);
    int i = left;
    int j = right + 1;
    for (;;) { // infinite for-loop, break to exit
        while (list.get(++i) < P)
            if (i >= right)
                break;
        // Now, list[i]≥P
        while (list.get(--j) > P)
            if (j <= left)
                break;
        // Now, list[j]≤P
        if (i >= j)
            break; // break the for-loop
        else
            // swap(list[i],list[j]);
            Collections.swap(list, i, j);
    }
    if (j == left)
        return j;
    // swap (list[left],list[j]);
    Collections.swap(list, left, j);
    return j;
}

查看演示运行 here .