C＃while循環不退出（quicksort）

由於某種原因，我的while循環（i < = j）不會在j比i更低時結束。C＃while循環不退出（quicksort）

我觀察了調試值，並且已經多次看到（4,3），（6,5）等的i和j（分別）的值。

public static List<Item> QuickSort(List<Item> a, int left, int right) 
{ 
    int i = left; 
    int j = right; 
    double pivotValue = ((left + right)/2); 
    Item x = a[Convert.ToInt32(pivotValue)]; 
    Item w; 
    while (i <= j) 
    { 
     //these while loops continue looping after i<=j is false 
     while (a[i] < x) 
     { 
      i++; 
     } 
     while (x < a[j]) 
     { 
      j--; 
     } 
     if (i <= j) 
     { 
      w = a[i]; 
      a[i++] = a[j]; 
      a[j--] = w; 
     } 
    } 
    if (left < j) 
    { 
     QuickSort(a, left, j); 
    } 
    if (i < right) 
    { 
     QuickSort(a, i, right); 
    } 
    return a; 
}

來源

2014-03-27 user3470510

這是一個遺憾...... – JustAndrei

我不相信'while while'壞了。繼續調試。也許這是遞歸？ – Benesh

它永遠不會去遞歸。這發生在第一遍。 – user3470510

我敢打賭，它要麼遞歸或內部的一個while循環了仍在繼續。我沒有記憶快速排序算法，但我敢打賭，如果你在調試器中闖入，你會發現自己處於兩個內部while循環之一中。

來源

2014-03-27 21:59:49

除了'a [pivotValue]'保證會破壞這些內部循環，因爲它不會大於或小於它自己（當'i'或'j'等於'pivotValue'時] – Sam

它確實通過（a [i ] user3470510

x有什麼價值？ –

編碼quicksort是一個非常好的練習，它不像看起來一切正常一樣容易！ ;）

這是您的代碼有一個問題。考慮如果j碰撞到關鍵點會發生什麼，而i不會。您將數據透視表（j）與i的數值進行交換，並通過數據透視表增加i。這不能繼續正確（如果你理解Quicksort，你應該明白爲什麼）。

選擇支點後，我喜歡與一個約束（無論是left或right）更換它，去交換價值，直到i和j見面，然後把支點回到了這個地方。當然還有其他方法。

來源

2014-03-27 22:22:27 jods

這不是一個無限循環。

while (a[i] < x) 
    { 
     i++; 
    }

如果x在列表中人數最多的，這將提高「我」只要陣列是超出範圍，和PROGRAMM將拋出一個OutOfRangeException。

來源

2014-03-27 22:22:38 hash

這並不能解釋所有事情......因爲'i'開始時等於'left'和'left <= pivot' by construction，'while（a [i] jods

如果i==j和a[i]==x ...會發生什麼？沒有增量，沒有減量，只是交換和繼續...

考慮將while(i<=j)更改爲while(i<j)。如果i==j ...

來源

2014-04-04 21:36:41 CiaPan

C＃while循環不退出（quicksort）

回答

相關問題