java - 使这个 QuickSort Java 程序变得更好

Question

已关闭。这个问题是 off-topic 。目前不接受答案。

---

想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。

已关闭12 年前。

Improve this question

我有这个 QuickSort 程序，我想这可能不是最好的解决方案，我想要关于我可以做的优化的想法。我计划在大约 2000 万个整数上运行它。

public static ArrayList<Comparable> quickSort(ArrayList<Comparable> arrayToSort) {
    if(arrayToSort.size() <= 0) {
        return arrayToSort;
    }
    Comparable pivot = arrayToSort.get(0);
    arrayToSort.remove(pivot);
    return quickSort(arrayToSort, pivot);
}

private static ArrayList<Comparable> quickSort(ArrayList<Comparable> arrayToSort, Comparable pivot) {
    ArrayList<Comparable> smaller = new ArrayList<Comparable>();
    ArrayList<Comparable> bigger = new ArrayList<Comparable>();

    for(Comparable i: arrayToSort) {
        if(i.compareTo(pivot) > 0) {
            bigger.add(i);
        } else {
            smaller.add(i);
        }
    }
    ArrayList<Comparable> retVal = new ArrayList<Comparable>();

    retVal.addAll(quickSort(smaller));
    retVal.add(pivot);
    retVal.addAll(quickSort(bigger));

    return retVal;
}

谢谢

Answer 1

1. 使用introsort而不是快速排序。
2. 使用三中位数或随机主元选择。
3. 使用 Fork/Join 进行并行化.