LinkedList的递归快速排序

Question

我一直在尝试在使用LinkedList的算法中实现递归快速排序。然而，当我运行该方法时，即使对于一个小列表(10个元素)，它似乎也会永远持续下去，我一直在等待该方法停止大约10分钟。

这是讨论的代码

public static void QuickSort(LinkedList<Contacto> Lista, int ini, int fin){
    Contacto pivote, aux;
    int i, j, comp;

    if (ini<fin){
        pivote = Lista.get(ini);
        i=ini+1;
        j=fin;
        while (i<j){
            while(i<fin && (comp=Lista.get(i).get_name().compareTo(pivote.get_name()))<=0 )
                i++;
            while((comp=Lista.get(i).get_name().compareTo(pivote.get_name()))>0 )
                j--;
            if(i<j){
                aux = Lista.get(i);
                Lista.set(i, Lista.get(j));
                Lista.set(j, aux);
                }
            }
        aux=Lista.get(j);
        Lista.set(j,pivote);
        Lista.set(ini,aux);
        QuickSort(Lista,ini,j-1);
        QuickSort(Lista,j+1,fin);
    }
}

谢谢你的帮助!

Answer 1

正如在评论中所指出的，它花费十分钟对十个项目的列表进行排序的事实是由于某个地方的错误，我建议您插入一些断点/println()语句，以了解您的方法是如何进行的(在每个条件的顶部一个应该足以显示它在哪里被挂起)。

也就是说，短列表的低效率是快速排序算法的一个已知问题——如果你考虑算法是如何工作的，你就会明白为什么它是一个固有的问题。(我可以详细解释，但如果你自己找出原因，你会更好)。

这个问题的一个常见解决方案是使用截断:当列表的大小小于截断大小时，切换到简单的插入排序来完成这项工作。这里有一个很好的讨论，这里有一个很好的实现示例。

注意该示例中quicksort()方法的前几行:

private static void quicksort(Comparable [] a, int left, int right) {
    final int CUTOFF = 3;
    if (right-left+1 < CUTOFF) { // if less than three elements remain: 
         insertionSort(a,left,right);
    else { //quicksort...

(注意:第一个链接来自《算法》第四版，由普林斯顿的一些人编写。我非常推荐这个网站，因为你正在通过基本算法进行推理)