5

众所周知,在快速排序中,您可以使用 Lomuto-Partition。我检查了很多参考资料,几乎所有参考资料都提出了以下实现:

int L_partition(int *a, int l, int r)
{
    int i, j, p, t;

    p = a[r];
    i = l - 1;

    for(j =l; j <= r-1; j++) {
        if(a[j] <= p) {
            i++;

            t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    }

    t = a[i+1];
    a[i+1] = a[r];
    a[r] = t;

    return i+1;
}

我的问题是为什么il-1开头并拥有所有i+1的东西?我认为从l开始就可以了。我测试下面的程序。它给出了与上述结果相同的结果。这比上面的要简单得多。

int L_partition2(int *a, int l, int r)
{
    int i, j, p, t;

    p = a[r];
    i = l;

    for(j = l; j <= r-1; j++) {
        if(a[j] <= p) {
            t = a[j];
            a[j] = a[i];
            a[i] = t;

            i++;
        }
    }

    t = a[i];
    a[i] = a[r];
    a[r] = t;

    return i;

}
4

1 回答 1

0

这与您只是改变i.

请注意,您在交换之后增加 i ,因为您的从一开始就有效,并且原始版本在交换之前增加它。但重要的是交换始终使用相同的元素(在您的版本和原始版本中)。

于 2013-10-02T09:34:05.080 回答