众所周知,在快速排序中可以使用 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;
}
我的问题是为什么 i 以 l-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;
}
这和你只是改变了
i
的用法是完全一样的。
请注意,您在交换后递增 i,因为您的 i 从一开始就有效,而原始版本在交换之前递增 i。但重要的是交换始终使用相同的元素(在您的版本和原始版本中)。
也许
i
代表左边有序数组的最后一个下标。