一个关于快排的百思不得其解的问题
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测，貌似也没发现什么问题啊，而且还能节约大量的时间。。。难道我的用例不够刁钻。。。 --------------------编程问答-------------------- 你得用很多测试用例才能发现错误，我不是说你错了，我还没有仔细看代码呢。
--------------------编程问答--------------------
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)
end
def quick_sort(array)
a = array.clone
quick_sort_internal(a, 0, a.size - 1)
return a
end
你可以对照一下，有啥出入没？ --------------------编程问答--------------------
我测了好几组。。。都没问题。。。当然我也知道这也不能说明没问题。。。可是我实在想不出来要怎么测了。。。 --------------------编程问答--------------------
不懂Ruby，我只能连猜带蒙的读。。。你的代码应该是和书上一致的，但是按我的写，内循环的那个while break if条件应该是i2==i1 --------------------编程问答-------------------- 没仔细看 赶紧楼主必成大器
--------------------编程问答--------------------
http://baike.baidu.com/link?url=D-Tk9GXp1LMcOa0AvZ2zIHUjNPZFXeqhoaCFC3Hf_d02pQ8SoJ3zmjotnGMu_3C30Q1QDd_bVKzHbsFWiMDKtq下面有JAVA的算法 --------------------编程问答-------------------- 你用lftIdx和用i的不同，是用i的话j不可能等于i，lftIdx的话就有可能。这里有一些情况会错，我暂时没时间举具体的例子，不过肯定会错的 --------------------编程问答-------------------- 刚仔细看了一下 感觉你这个快排算法有点混乱 你的算法是
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
你每走一次的结果是什么 应该更有参考意义 --------------------编程问答--------------------
我在纠结的就是，到底在什么情况下会出错。。。脑壳都想痛了
--------------------编程问答--------------------
事情是这样的。。。你把我外循环之后的语句给吃了。。。呐，我两个循环结束之后的结果的确是4 1 2 3 6 5，但是呢，之后还有一个交换的操作，是把5和6进行交换。
tmp = array[ i ];--------------------编程问答-------------------- 顶上去接着求解
array[ i ] = array[ ritIdx ];
array[ ritIdx ] = tmp;
补充：Java , Java SE
