快速排序划分算法 [英] 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屋！