java 中的快速排序列表

Question

我正在尝试使用 java 练习快速排序列表，我认为这是正确的，但它显示 "Exception in thread main..."

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。

Answer 2

试试这个：

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 (from < to) {
        int pivot = from;
        int left = from + 1;
        int right = to;
        int pivotValue = list.get(pivot);
        while (left <= right) {
            // left <= to -> limit protection
            while (left <= to && pivotValue >= list.get(left)) {
                left++;
            }
            // right > from -> limit protection
            while (right > from && pivotValue < list.get(right)) {
                right--;
            }
            if (left < right) {
                Collections.swap(list, left, right);
            }
        }
        Collections.swap(list, pivot, left - 1);
        sort(list, from, right - 1); // <-- pivot was wrong!
        sort(list, right + 1, to);   // <-- pivot was wrong!
    }
}

java 中的快速排序列表

quick sort list in java

java

list

quicksort