java - 快速排序：这个实现有什么问题

Question

你能解释一下这个在java中实现的快速排序算法有什么问题吗？

static ArrayList<Integer> quickSort(ArrayList<Integer> array){

    if (array.size() <=1){
        ArrayList<Integer> a = new ArrayList<Integer>();

        return a;
    }

    int pivotIndex = array.size() / 2;

    int pivot = array.get(pivotIndex);
    ArrayList<Integer> left= new ArrayList<Integer>();
    ArrayList<Integer> right = new ArrayList<Integer>();

    for (int i = 0; i < array.size(); i++) {
        if (i!=pivotIndex){
        if (array.get(i) > pivot)
            right.add(array.get(i));
        else
            left.add(array.get(i));
        }

    }
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.addAll(quickSort(left));
     l.add(pivot);
     l.addAll(quickSort(right)); 

    return l;

}

Answer 1

代替

if (array.size() <=1) {
    ArrayList<Integer> a = new ArrayList<Integer>();

    return a;
}

利用

   if (array.size() <=1){
   return array
}

Answer 2

一个明显的错误是未正确处理大小为 1 的数组。正确处理这一点很重要，因为这是递归的基本情况之一。

Answer 3

该算法的主要问题 - 您正在为函数的每次调用创建新的 ArrayLists。通过这种方式，您可以取消快速排序的最佳功能 - 无需任何额外内存即可就地排序。尝试只使用第一个给定的数组。