void partition(int *a, int size) {
int pivot = a[0];
int left = 0, right = 0;
for(left = 1, right = size-1; left <= right; left++, right--) {
if(a[left] >= pivot && a[right] <= pivot){
swap(left, right, a);
}
}
swap(0, right, a);
}
我写了这个方法来划分的阵列,以一个preliminary一步申请快速排序,我测试了这个样本数据:
I wrote this method to partition an array as a preliminary step in order to apply quick sort, I tested it on this sample data:
8 2 5 13 4 19 12 6 3 11 10 7 9
正确的输出应该是:
the correct output should be:
6 2 5 7 4 3 8 12 19 11 10 13 9
但实际产量为:
but the actual output is:
6 2 5 13 4 3 8 12 19 11 10 7 9
该算法交换 13
与 7
,但它未能由于&放;&安培;
情况在上述循环。我想增加离开
仅 A [左]≥=支点
和减量权
仅 A [右]&LT; =支点
The algorithm has to swap 13
with 7
but it fails due to the &&
condition in the above loop. I want to increment left
only if a[left] >= pivot
and decrement right
only if a[right]<= pivot
.
您或多或少地回答了你自己的问题。你可能想要做这样的事情:
You more or less answered your own question. You probably want to do something like this:
void partition(int *a, int size) {
int pivot = a[0];
int left, right;
for(left = 1, right = size-1; left < right; )
{
if(a[left] > pivot && a[right] <= pivot)
{
swap(left, right, a);
}
if(a[left] <= pivot) left++;
if(a[right] > pivot) right--;
}
}