众所周知,在快速排序中,您可以使用 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;
}