C++ 快速排序分区算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13782209/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Quick sort partition algorithm
提问by Java Player
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);
}
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
The algorithm has to swap 13with 7but it fails due to the &&condition in the above loop. I want to increment leftonly if a[left] >= pivotand decrement rightonly if a[right]<= pivot.
该算法必须交换13，7但由于&&上述循环中的条件而失败。我只想在leftif 时增加，只有 if时才a[left] >= pivot减少。righta[right]<= pivot
回答by JasonD
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--;
}
}
回答by user3210502
here is another option, little bit more similar to the original one
这是另一种选择，与原始选择更相似
int partition(int arr[], int left, int right)
{
int pivot = arr[left];
while (left != right)
{
if (arr[left] > arr[right])
{
swap(arr[left], arr[right]);
}
if (pivot == arr[left])
right--;
else // Pivot == arr[right]
left++;
}
return left;
}
