快速排序分区算法

• Z时代
• 2024-01-10
• 分类：问答

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);
}

为了进行快速排序，我编写了此方法来对数组进行分区，这是准备进行快速排序的第一步，并在此示例数据上对其进行了测试：

8 2 5 13 4 19 12 6 3 11 10 7 9

正确的输出应为：

6 2 5 7 4 3 8 12 19 11 10 13 9

但实际输出为：

6 2 5 13 4 3 8 12 19 11 10 7 9

该算法必须交换13，7但由于&&上述循环中的条件而失败。我想增加left只有a[left] >=

pivot和递减right仅当a[right]<= pivot。

回答：

您或多或少地回答了自己的问题。您可能想要执行以下操作：

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--;
    }
}

以上是 快速排序分区算法 的全部内容， 来源链接： utcz.com/qa/400056.html