Java快速排序错误

Question

我正在为数组中的字符串快速排序程序，我不确定我在做什么错误 - 它打印出错误的答案。

public static void quickSort(String[] s, int beg, int end){ 
    int i = beg, j = end; 

    if(end-beg >= 1){ 
     String piv = s[beg]; 
     while(j > i){ 
      while(s[j].compareTo(piv) > 0 && j >= i && i >= beg) 
       j--; 
      while(s[i].compareTo(piv) <= 0 && j > i && i <= end) 
       i++; 
      if(j > i){ 
       String temp = s[i];   
       s[i] = s[j];  
       s[j] = temp;   
      } 

      for(String k : s) 
       System.out.print(k); 
      System.out.println(); 

      quickSort(s, beg, j-1); 
      quickSort(s, j+1, end); 

     } 
    } 

如果我输入{r, t, c, x, a, w, p}例如，我得到 r p c x a w t重复14次。请帮忙！

Answer 1

试试这个代码：

private static void quickSort(String[] s, int beg, int end) { 
    int i = beg, j = end; 

    if (end-beg >= 1) { 
     String piv = s[beg]; 
     while (j >= i) { 
      while (s[i].compareTo(piv) < 0) { 
       i++; 
      } 
      while (s[j].compareTo(piv) > 0) { 
       j--; 
      } 
      if (j >= i) { 
       String temp = s[i]; 
       s[i] = s[j]; 
       s[j] = temp; 
       i++; 
       j--; 
      } 
     } 

     for(String k : s) 
      System.out.print(k); 
     System.out.println(); 

     quickSort(s, beg, j); 
     quickSort(s, i, end); 

    } 
} 

我试着坚持你最初的实现尽可能多的。正如彼得说，有几件事情错的原代码，但如果你比较细微的差别我认为这将是有意义的。

Answer 2

这里有很多问题，你用过我的意思是j和j，你的意思是我至少有两次。如果你按照维基百科上发现就地快速排序，你实际上并不需要保持既有i和j。我会建议从头开始，并按照维基百科的puesdo代码如下发现：

// left is the index of the leftmost element of the subarray 
    // right is the index of the rightmost element of the subarray (inclusive) 
    // number of elements in subarray = right-left+1 
    function partition(array, left, right, pivotIndex) 
    pivotValue := array[pivotIndex] 
    swap array[pivotIndex] and array[right] // Move pivot to end 
    storeIndex := left 
    for i from left to right - 1 // left ≤ i < right 
     if array[i] <= pivotValue 
      swap array[i] and array[storeIndex] 
      storeIndex := storeIndex + 1 // only increment storeIndex if swapped 
    swap array[storeIndex] and array[right] // Move pivot to its final place 
    return storeIndex