java - Quicksort分而治之

我试图使用分治技术实现快速排序递归调用中出现堆栈溢出错误这是我的代码：

public static void main(String[] args) {
    ArrayList<Integer> unsorted = new ArrayList<Integer>();

    unsorted.add(23);
    unsorted.add(5);
    unsorted.add(1);
    unsorted.add(-8);
    unsorted.add(101);
    unsorted.add(21);
    unsorted.add(10);
    unsorted.add(10);
    unsorted.add(0);
    unsorted.add(50);

    ArrayList<Integer> sorted = Quicksort(unsorted);
    System.out.println(sorted.toString());
}

public static ArrayList<Integer> Quicksort(ArrayList<Integer> unsorted) {

    if (unsorted.size() <= 1)
        return unsorted;

    ArrayList<Integer> less = new ArrayList<Integer>();
    ArrayList<Integer> more = new ArrayList<Integer>();

    int pivotindex = unsorted.size()/2;

    for (int i = 0; i < unsorted.size(); i++) {
        if (unsorted.get(i) < unsorted.get(pivotindex))
            less.add(unsorted.get(i));
        else
            more.add(unsorted.get(i));
    }

    ArrayList<Integer> sorted = Quicksort(less);
    sorted.add(unsorted.get(pivotindex));
    sorted.addAll(Quicksort(more));

    return sorted;
}

我希望它使用ArrayLists实现有人能指出我错在哪里吗？
谢谢。

最佳答案

您应该将pivot值与more和less列表分开放置。
将条件更改为：

else if(unsorted.get(i) > unsorted.get(pivotindex))
        more.add(unsorted.get(i));

它应该工作得很好希望这有帮助。
编辑：正如Josh在评论中提到的，如果有多个元素具有与pivot相同的值，这就不起作用为此，您可以定义另一个名为equal的arraylist并添加此行：

else
    equal.add(unsorted.get(i));

然后在合并数组时将此列表与pivot元素一起追加。
谢谢你指出这一点:)
注意：不能保证这种排序是稳定的（因为具有相同值的元素可能不会根据它们在原始数组中的相对位置放置）。

关于java - Quicksort分而治之，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45987761/