快速排序 Java 方法

Question

我对这种方法的输出有疑问：

static void quickSort(int[] ar) {

    ArrayList<Integer> left = new ArrayList<Integer>();
    ArrayList<Integer> equal = new ArrayList<Integer>();
    ArrayList<Integer> right = new ArrayList<Integer>();
    int num = ar[0];
    for (int i = 0; i < ar.length; i++) {
        if (ar[i] < num) {
            left.add(ar[i]);
        } else if (ar[i] > num) {
            right.add(ar[i]);
        } else {
            equal.add(ar[i]);
        }
    }
    int[] l = listToArray(left);
    int[] e = listToArray(equal);
    int[] r = listToArray(right);
    ArrayList<Integer> combined = new ArrayList<Integer>();
    combined.addAll(left);
    combined.addAll(equal);
    combined.addAll(right);
    int[] c = listToArray(combined);

    if (l.length > 1) {
        quickSort(l);
    }

    if (r.length > 1) {
        quickSort(r);
    }
    printArray(c);
}

输入（标准输入）

7

5 8 1 3 7 9 2

你的输出（标准输出）

2 3

1 3 2

7 8 9

1 3 2 5 8 7 9

预期输出

2 3

1 2 3

7 8 9

1 2 3 5 7 8 9

Answer 1

有些地方出了问题。 1) 对于快速排序，您必须先左右排序，然后再将它们组合回组合数组。

2) combined.addAll() 未按预期运行。当我有 {2,3} 时，它以相反的顺序附加它们。在这里，我已经将手册中的值传递给循环。

3) 对于快速排序到 return 其值，必须将它们重新填充回原始参数或作为值 returned。我在原来的参数里填好了。

static void quickSort(Integer[] ar) {

    ArrayList<Integer> left = new ArrayList<Integer>();
    ArrayList<Integer> equal = new ArrayList<Integer>();
    ArrayList<Integer> right = new ArrayList<Integer>();
    int num = ar[0];
    for (int i = 0; i < ar.length; i++) {
        if (ar[i] < num) {
            left.add(ar[i]);
        } else if (ar[i] > num) {
            right.add(ar[i]);
        } else {
            equal.add(ar[i]);
        }
    }
    Integer[] l = new Integer[0];
    l = left.toArray(l);
    Integer[] e = new Integer[0];
    e = equal.toArray(e);
    Integer[] r = new Integer[0];
    r = right.toArray(r);
    if (l.length > 1) {
        quickSort(l);
    }

    if (r.length > 1) {
        quickSort(r);
    }
    ArrayList<Integer> combined = new ArrayList<Integer>();
    for(int ai = 0; ai < l.length; ai++)
    {
        combined.add(l[ai]);
    }
    for(int ai = 0; ai < e.length; ai++)
    {
        combined.add(e[ai]);
    }
    for(int ai = 0; ai < r.length; ai++)
    {
        combined.add(r[ai]);
    }
    combined.toArray(ar);
    //printArray(ar);
    System.out.println(combined);
}

快速排序 Java 方法

Quicksort Java method

java

sorting

quicksort