C语言 Lomuto-快速排序中的分区

368yc8dk  于 2023-11-16  发布在  其他
关注(0)|答案(2)|浏览(123)

正如我们所知,在快速排序中,你可以使用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;

}

bvuwiixz

bvuwiixz1#

这和你只是改变i的用法是完全一样的。
请注意,在交换之后,i是递增的,因为你的i从一开始就有效,而原始版本在交换之前会递增i。但重要的是,交换总是使用相同的元素(在你的版本和原始版本中)。

ma8fv8wu

ma8fv8wu2#

也许i表示左边有序数组的最后一个下标。

相关问题