快速排序偶爾沒有完成？

我已經做了一堆嘗試快速排序算法，我似乎無法工作。這段代碼是我得到的最接近的代碼，除了大約五分之一的代碼沒有完全排序 - 它輸出的內容類似於266, 186, 219, 276, 357, 405, 686, 767, 834, 862。我試圖找到所有這些數字集之間的共同點，但我找不到任何東西。我用調試器花了好幾個小時，但看不到任何東西（儘管我覺得我錯過了一些明顯的東西）。我究竟做錯了什麼？快速排序偶爾沒有完成？

public static void sort(ArrayList<Integer> arr, int left, int right) { 
    int i = left - 1, j = right, v = arr.get(right); 
    if(right - i == 0 || right - i == 1)return; 

    for(;;) { 
     while(arr.get(++i) < v); 
     while(v < arr.get(--j) && j != 0) 
      if(j == 1)break; 
     if(i >= j)break; 

     Collections.swap(arr, i, j); 
    } 
    Collections.swap(arr, i, right); 

    sort(arr, left, i - 1); 
    sort(arr, i, right); 
}

來源

2015-04-27 IHazABone

你的第一個數字是不排序的東西，所以這就是我開始看的地方 –

一步一步地在紙上跟蹤它。在每一步記錄下每個變量的值和數組的變化。不要寫下你認爲應該的內容，寫下指示實際說的內容。當你用這種方式追蹤它時，你會對事物有更好的理解。 – kojow7

我現在就去做，謝謝。由於它經歷了多少次迭代（這意味着紙上有數百行），所以我暫時放棄這一點。 – IHazABone

我做了兩件事情對你的代碼來得到它的工作：

在方法的開始設置j = right +1 和移動v = arr.get(right)先if語句之後。

應該是這個樣子：

public static void sort(ArrayList<Integer> arr, int left, int right) { 
     int i = left - 1; 
     int j = right + 1; 
     if (right - i == 0 || right - i == 1) return; 
     int v = arr.get(right); 

     for (;;) { 
      while (arr.get(++i) < v); 
      while (v < arr.get(--j) && j != 0) 
       if (j == 1) break; 
      if (i >= j) break; 

      Collections.swap(arr, i, j); 
     } 
     Collections.swap(arr, i, right); 

     sort(arr, left, i - 1); 
     sort(arr, i, right); 
    }

但是，這是真的不可讀的代碼，你應該讀的書CleanCode。

來源

2015-04-27 21:19:41 osundblad

下次我有機會嘗試一下，但是至於我的代碼「真的不可讀」，你所做的只是將頂部的變量聲明分開。 – IHazABone

爲什麼List而不是ArrayList？ – IHazABone

更改列表返回到ArrayList是否可以編寫單元測試，而不會導致我的IDE大量警告。 – osundblad

快速排序偶爾沒有完成？

回答

相關問題