Java中Quicksort的问题

所以我一直在测试不同的排序算法，现在我写了一个Quicksort！它的作品，但排序有点偏离！几乎总是我得到这样的输出：Java中Quicksort的问题

[0, 1, 2, 3, 8, 6, 5, 4, 7, 9, 20, 16, 22, 21, 14, 17, 18, 10, 15, 19, 13, 11, 23, 12, 26, 24, 25, ...

这是我排序的100中的前27个元素。这就是我如何填写随机列表：

for(int i =0; i < 100; i ++){ 
      int nr = rand.nextInt(100); 
      if (!numbers.contains(new Integer(nr))){ 
       numbers.add(nr); 
      }else { 
       i--; 
      } 
}

这里是快速排序的代码：

public class Quicksort{ 
@SuppressWarnings("unchecked") 
static public <T> ArrayList<T> sortting(ArrayList<T> t){ 
    //System.out.print("-"); 
    T piv; 
    ArrayList<T> left ,right ,newT; 
    left = new ArrayList<T>(); 
    right = new ArrayList<T>(); 
    newT = new ArrayList<T>(); 

    if (!t.isEmpty()){ 
     piv = t.get(t.size()/2); 
     for (int i =0; i < t.size(); i++){ 
      if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left 
       left.add(t.get(i)); 
      }else{ //right 
       right.add(t.get(i)); 
      } 
     } 

     if (left.isEmpty() || right.isEmpty()){ 
      newT.addAll(left); 
      newT.addAll(right); 
      return newT; 
     }else { 
      right = sortting(right); 
      left = sortting(left); 

      newT.addAll(left); 
      newT.addAll(right); 
     } 

     return newT; 
    } 
    return null; 

} 

}

来源

2013-07-18 Bardia ' Luviz' Jedi

你的问题是与此块：

if (left.isEmpty() || right.isEmpty()){ 
     newT.addAll(left); 
     newT.addAll(right); 
     return newT; 
    }

如果您选择在枢轴有些观点恰好是当前子列表中最小的，然后该子列表会自动被认为是排序的。您应该删除该检查并对左侧和右侧子列表进行排序。

这是好的，因为然后你会进入一个空列表的递归调用，在这种情况下，你返回null。

if (!t.isEmpty()){ ... return newT;} 
return null;

实际上，我不知道，如果ArrayList.addAll()处理null投入正常。如果你担心这一点，那么你可以返回一个空的ArrayList而不是null。

来源

2013-07-18 00:44:29 bdares

但如果我删除检查我怎么知道，当算法需要停止/结束 –

好吧我已经尝试，但仍然没有工作顺便说一句我已经改变了'返回null'到'返回新ArrayList <>（）;'应该是一个空阵！在常见问题解答中，问题在于右侧向一个inf循环中溢出了内存。这意味着我看到右侧被迫停止，因为左侧是空的，但前面的右侧不会停止！ –

粘性你bdares您输入您指出了一些无能的部分，帮助配发！但是，这不是问题

的问题是，枢不从MEAS数组中删除，如果枢轴是最小的元素正确的数组==到t导致无限循环并超载RAM！

例如。

5 ,4 ,8 ,6 ,8 will return 5 ,4 ,8 ,6 ,8

所以为了解决这个枢轴需要删除和重新附加在阵列的开始

现在

5 ,4 ,8 ,6 ,8 will return 4 ,5 ,8 ,6 ,8

这里是源代码，如果你有兴趣，和专家提示：所有的方式确保至少有一个小的变化是思考你的迭代

@SuppressWarnings("unchecked") 
static public <T> ArrayList<T> sortting(ArrayList<T> t){ 

    T piv; 
    ArrayList<T> left ,right ,newT; 
    left = new ArrayList<T>(); 
    right = new ArrayList<T>(); 
    newT = new ArrayList<T>(); 

    if (!t.isEmpty()){ 
     if (t.size()==1){  //Finish check -> one elem is sorted 
      return t; 
     }  
     piv = t.remove(t.size()/2); 
     for (int i =0; i < t.size(); i++){   //sorting 
      if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left 
       left.add(t.get(i)); 
      }else{ //right 
       right.add(t.get(i)); 
      } 
     } 
     right = sortting(right); //sub sorting 
     left = sortting(left); 

     newT.addAll(left);  //building newT 
     newT.add(piv); 
     newT.addAll(right); 
     return newT; 
    } 
    return new ArrayList<>(); 
}

来源

2013-07-18 15:10:53

Java中Quicksort的问题

回答

相关问题