Quicksort Divide and Conquer

Question

我正在尝试使用分而治之技术来实现Quicksort.我在递归调用中收到Stack Overflow错误.这是我的代码:

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.任何人都可以指出我错在哪里吗？

非常感谢.

Answer 1

您应该将您的pivot价值保持在more和less列表分开的位置.

将条件更改为:

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

它应该工作正常.希望这可以帮助.

编辑:正如Josh的评论中提到的,如果有多个元素与枢轴具有相同的值,则这将不起作用.为此,您可以做的是定义另一个被调用的ArrayList equal并添加以下行:

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

然后pivot在合并数组时将此列表与元素一起追加.

感谢您指出了这一点.:)

注意:这种排序不能保证稳定(因为具有相同值的元素可能不会根据它们在原始数组中的相对位置放置).