クイックソート - 理由は小切手ウェブ上

Question

多くの例（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)を持っているかどうか私の理解から、私たちは基本的に同じ値を同じ値に交換します。

誰でも私のためにそのパズルを解くことができますか？

Answer 1

条件がi < jに置き換えられたとします。

：whileループは、我々はクイックソートを関数の呼び出しを重ねているだろうし、これらの呼び出しはだろう i = 2と j = 2、および で終了します

5,4,3,2,1 

：

は次のように配列のために何が起こるか見てみましょう

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

この条件がある場合、i<=jループはi = 4とj = 1で終了します電話は：

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

などのコールがあります。

だから、基本的にあなたがすぐそこに同じ要素を交換するにはポイントがありませんが、コードの作者はあなたが私はjの

に等しい場合にスワップする必要がいけないの余分な条件を追加するための必要性を回避するためにそれを省略している必要があります