實現快速排序

的下面快速排序代碼來自programming pearls 實現快速排序

void qsort3(int l, int u) 
{ int i, j; 
    DType t; 
    if (l >= u) 
     return; 
    t = x[l]; 
    i = l; 
    j = u+1; 
    for (;;) { 
     do i++; while (i <= u && x[i] < t); 
     do j--; while (x[j] > t); 
     if (i > j) 
      break; 
     swap(i, j); 
    } 
    swap(l, j); 
    qsort3(l, j-1); 
    qsort3(j+1, u); 
}

在雙向劃分部分，有一行：

if (i > j)

我的問題是我可以改變此行爲：

if(i >= j)

我認爲這樣做的原因是： (i==j) < =>(x[i] == t)因此我們不需要 swap x [i]和x [j]。我們只是打出for循環。

for循環的以下代碼是swap(l, j)。由於x [j] == t == x [l]，swap(l, j)沒有任何東西可以用做分區。

感謝

來源

2012-10-09 Fihop

我沒有看過任何代碼，但本能地說，quicksort的某些實現是穩定排序，意味着將保留相同元素的相同元素順序。使用'if（i> = j）'*可能會搞砸了。純粹的猜測雖然 –

@ AK4749：不，quicksort一般*不是一個穩定的排序算法。 – digitalvision

@digitalvision是我的壞，記得它不正確，有效的版本不是 –

我要說的是，是的，你可以做出的改變：

掉期（I，J）是吃力不討好的，當我== j和之後的下一個迭代i ==Ĵ無條件遞增i並遞減j，並且因此將導致循環終止，無論如何不改變數組。

來源

2012-10-09 18:12:51

實現快速排序

回答

相關問題