开发者

Make this QuickSort Java Program better [closed]

Closed. This question is off-topic. It is not currently accepting answers. 开发者_运维问答

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

I have this QuickSort program, I am thinking maybe it's not the best solution, I want ideas on Optimizations I could do. I plan on running it on about 20Million integer numbers.

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;
}

Thanks


  1. Use introsort instead quicksort.
  2. Use median-of-three or randomized pivot selection.
  3. Parallelize using Fork/Join.
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜