在某些情况下

-1

快速排序不工作当我测试我的快速排序我注意到另一个问题。有时它按字母顺序排列数组，有时它不会。例如，如果我有p, o, j, l作为我的阵列，它将它排序为j, o, l, p，这是错误的，因为l应该在o之前。但是，如果我将a添加到阵列，它排序为a, j, l, o, p这是正确的。这是为什么发生？在某些情况下

代码：

private ArrayList<String> sort(ArrayList<String> ar, int lo, int hi){ 
     if (lo < hi){ 
      int splitPoint = partition(ar, lo, hi); 
      sort(ar, lo, splitPoint); 
      sort(ar, splitPoint +1, hi); 
     } 
     return ar; 
    } 

    private int partition(ArrayList<String> ar, int lo, int hi){ 
     String pivot = ar.get(lo); 
     lo--; 
     hi++; 
     while (true){ 
      lo++; 
      hi--; 
      while (lo<hi && ar.get(lo).compareTo(pivot) < 0){ 
       lo++; 
      } 
      while (hi>lo && ar.get(hi).compareTo(pivot) >= 0){ 
       hi--; 
      } 
      if (lo<hi){ 
       swap(ar, lo, hi); 
      }else { 
       return hi; 
      } 
     } 
    } 

    private ArrayList<String> swap(ArrayList<String> ar, int a, int b){ 
     String temp = ar.get(a); 
     ar.set(a, ar.get(b)); 
     ar.set(b, temp); 
     return ar; 
    }

来源

2014-02-08 Cristian Gutu

据我所看到的，你不改变主元的位置。你只是交换你好。

最后，您应该将枢轴放在正确的位置，然后将其返回。

来源

2014-02-08 16:52:11

我一直比较和交换，而'LO

据我了解，最初lo == pivot。因此，arr [lo]与arr [pivot]的第一次比较应为零，并且lo将递增。枢轴应保持在其位置。 –

正确。但我不移动关键点，我只是重新排列这些值。奇怪的是它在除了这个之外的其他所有情况下都有效。 –

我认为在循环的最后一次迭代中存在危险。

假设你有一个数组2,1。

你的枢轴为2

所述LO指数增加，直到它找到的1的枢轴上方的元件或满足喜。在这种情况下，将满足HI和LO都和高保真将指向1

在这一点上你的分区函数返回，并报告阵列已经被划分为：

{2},{1}

但是，这是不正确，因为1是<比枢轴所以应该在第一个分区。

也许当你遇到嗨，你应该执行一个额外的测试，以查看hi中的元素是否应该包含在左边或右边的分区中？

来源

2014-02-08 17:42:12

在某些情况下

回答

相关问题