一个关于快排的百思不得其解的问题

Question

private void recQuickSort1( int lftIdx, int ritIdx ) {
int mid;
if( lftIdx >= ritIdx )
  return;
else {
mid = partitioning1( lftIdx, ritIdx, array[ ritIdx ] );
recQuickSort1( lftIdx, mid - 1 );
recQuickSort1( mid + 1, ritIdx );
}
} private int partitioning1( int lftIdx, int ritIdx, int pivot ) {
showArray();
int i = lftIdx, j = ritIdx - 1, tmp;
while( true ) {
while( array[ i ] < pivot )
  i++;
while( lftIdx < j && array[ j ] > pivot ) //就是这里
  j--;
if( i >= j )
  break;
else {
tmp = array[ i ];
array[ i ] = array[ j ];
array[ j ] = tmp;
}
}
tmp = array[ i ];
array[ i ] = array[ ritIdx ];
array[ ritIdx ] = tmp;
return i;
} //End of partitioning
如上述代码中，为什么是lftIdx < j而不能是i < j呢我看好多书上都写的lftIdx < j，可是我用i < j测，貌似也没发现什么问题啊，而且还能节约大量的时间难道我的用例不够刁钻

Answer 1

def quick_sort_internal(a, from, to)
return if from >= to
m = a[to]
i1, i2 = from, to
while true
while m > a[i1]
i1 += 1
end i2 -= 1
while m < a[i2]
i2 -= 1
break if (i2 == from)
end break if i1 >= i2 a[i1], a[i2] = a[i2], a[i1]  end
a[i1], a[to] = a[to], a[i1] 
quick_sort_internal(a, from, i1 - 1)
quick_sort_internal(a, i1 + 1, to)
enddef quick_sort(array)
a = array.clone
quick_sort_internal(a, 0, a.size - 1)
return a
end
你可以对照一下，有啥出入没？

Answer 2

不懂Ruby，我只能连猜带蒙的读你的代码应该是和书上一致的，但是按我的写，内循环的那个while break if条件应该是i2==i1

Answer 3

http://baike.baidu.com/link?url=D-Tk9GXp1LMcOa0AvZ2zIHUjNPZFXeqhoaCFC3Hf_d02pQ8SoJ3zmjotnGMu_3C30Q1QDd_bVKzHbsFWiMDKtq
下面有JAVA的算法

Answer 4

你用lftIdx和用i的不同，是用i的话j不可能等于i，lftIdx的话就有可能。这里有一些情况会错，我暂时没时间举具体的例子，不过肯定会错的

Answer 5

刚仔细看了一下 感觉你这个快排算法有点混乱 你的算法是
         while( array[ i ] < pivot )
        i++;        
        while( lftIdx < j && array[ j ] > pivot )    //就是这里
         j--;
        if( i >= j )
        break;        
        else {交换array[i],array[j];}  试想一个排列 6 1 2 3 4 5
第一次调用的时候
你pivot存的5  i指向的是6 j指向的是4 运行一次上面的代码 i,j都不动 然后你会把6和4互换了
我理解的你的逻辑是： 找一个最右面的数pivot（5）  
然后从左面用i找一个比它大的（6） 然后从右面用j找一个比它小的（4）
然后交换i和j
操作完的结果是 4 1 2 3 6 5但是快排的逻辑应该是（这2步可以颠倒）：
找一个数（5） 然后用i找一个比它大的（6) 然后5和6换位置
找一个数（5） 然后用j找一个比它小的（4) 然后5和4换位置
操作完的结果是 4 1 2 3 5 6你再研究研究 看是不是这样 因为我只走了一圈代码 你再多走几圈
看看每一次面对排列 6 1 2 3 4 5
你每走一次的结果是什么 应该更有参考意义

Answer 6

事情是这样的你把我外循环之后的语句给吃了呐，我两个循环结束之后的结果的确是4 1 2 3 6 5，但是呢，之后还有一个交换的操作，是把5和6进行交换。
    tmp = array[ i ];
    array[ i ] = array[ ritIdx ];
    array[ ritIdx ] = tmp;