快速排序 - 理由等於檢查

許多例子在網絡上約快速排序（在Java中）正在接近這樣的：快速排序 - 理由等於檢查

private void quicksort(int low, int high) { 
    int i = low, j = high; 
    int pivot = numbers[low + (high-low)/2]; 

    while (i <= j) { 

     while (numbers[i] < pivot) { 
     i++; 
     } 

     while (numbers[j] > pivot) { 
     j--; 
     } 

     if (i <= j) { 
     exchange(i, j); 
     i++; 
     j--; 
     } 
    } 

    if (low < j) 
     quicksort(low, j); 
    if (i < high) 
     quicksort(i, high); 
}

我不解的是事情，爲什麼還有那些等於檢查：

1）while (i <= j)代替while (i < j)

2）if (i <= j)代替if (i < j)

這裏有沒有任何邊界情況等於關鍵？根據我的理解，如果我們有if(i == j)，那麼我們基本上會用相同的值交換相同的值。

任何人都可以爲我解決這個難題？

來源

2016-06-22 Lucas

你能發佈一個這樣的在線代碼的鏈接嗎？我認爲你是對的，與一個元素本身交換是沒有意義的 – shole

上面的代碼片段實際上來自於vogella博客。 – Lucas

假設條件被i < j代替。

讓我們看看會發生什麼樣的數組：

5,4,3,2,1

while循環將與i = 2和j = 2，並我們將不得不重複調用函數快速排序終止，這些電話將：

quicksort(0,2) and quicksort(2,4)

而如果我們確實有這個條件i<=j循環將終止於i = 4和j = 1現在我們wou ld的呼叫爲：

quicksort(0,1) and quicksort(3,4)

哪些是正確的呼叫。

所以基本上你就在那裏被交換相同的元素，但該代碼的作者沒有點必須省略，以避免添加你不需要的時候我等於Ĵ

換一個額外條件的需要

來源

2016-06-22 08:46:45

我明白了。它確實會重疊「2」索引，但它不會破壞算法到底會不會呢？你會告訴我，你會忽略上述代碼中的<=個案嗎？ – Lucas

是的，它肯定會破壞算法，如果我們有<而不是<=，因爲快速排序分區將數組分成兩個不相交的子陣列，而不與子數組重疊。 –

@Lucas我會做的唯一事情就是添加交換條件。這意味着只有當我！= j時我纔會交換。 –

快速排序 - 理由等於檢查

回答

相關問題