快速排序分区

Question

很抱歉我是个笨蛋，但我已经为自己的快速排序实现苦苦挣扎了一段时间。更具体地说，我无法让我的分区程序正常工作。可笑的是，我也尝试过几乎直接从 Sedjewick 的书中复制一个实现，但是没有成功。这是我的代码：

void partition(int a[], int size)
{
    int i, j = size - 1;
    int t, pivot = a[j / 2];
    i = 0;
    for (;;)
    {
        while (a[i] < pivot)
            i++;
        while (a[j] > pivot)
            j--;
        if (i >= j)
            break;
        t = a[i];
        a[i++] = a[j];
        a[j] = t;
    }
}

这里是输入的例子：

82, 65, 59, 10, 35, 51, 81, 47, 25, 64, 34, 38, 12, 38, 58, 74, 37, 42, 63, 18,
75, 67, 36, 77, 47, 48, 13, 91, 94, 52

这里的主元是 58，但我得到错误的输出：

52, 13, 48, 10, 35, 51, 47, 47, 25, 36, 34, 38, 12, 38, 18, 58, 37, 42, 63, 74,
75, 67, 64, 77, 81, 59, 65, 91, 94, 82

它看起来几乎正确，除了 37 和 42 紧跟在 58 之后。我尝试了很多不同的分区程序，但它们都让我满意相似的结果。

Answer 1

编辑

我之前的回答似乎解决了这个问题，但并不正确。

你的输出没问题。让我用竖线直观地指示分区：

52、13、48、10、35、51、47、47、25、36、34、38、12、38、18、58、37、42 || 63、74、75、67、64、77、81、59、65、91、94、82

垂直条左侧的所有值 <= 58，右侧的所有值 >= 58。这是快速排序中分区步骤的预期值。

但是，除了递增 i 之外，您还需要递减 j:

t = a[i];
a[i++] = a[j];
a[j--] = t; // added a decrement here

除此之外，您唯一缺少的是 return分区索引。只需 return 函数末尾 i 的值，并将其用作递归步骤中的数组边界。

Answer 2

将a[j] = t;替换为a[j--] = t

快速排序分区

Quicksort partitioning

sorting

partitioning

quicksort

partition