快速排序划分算法 [英] Quick sort partition algorithm
本文介绍了快速排序划分算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
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--;
}
}
这篇关于快速排序划分算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文