第一个很简单,从两侧步行直到找到回归点。
/*C++ version, [first, last), last needs --first to fetch the last element*/
/*returns the middle of partitioning result*/
int* partition( int *first, int *last, int pivot ) {
while (true) {
while (*first < pivot) ++first;
--last;//Don't edit this, it's true.
while (pivot < *last) --last;
if (!(first < last)) return first;
swap(*first, *last);
++first;
}
}
第二个(在“算法简介”中显示)是:
int* partition( int a[], int n, int pivot ) {
bound = 0;
for ( i = 1; i != n; ++i )
if ( a[i] < pivot )
swap( &a[i], &a[++bound]);
swap(a, a + bound);
return a + bound;
}
第二个不变量是“bound之前的所有元素都小于pivot”。
问:这两个版本的优缺点是什么?
我先给出一个,第二个需要对迭代器(指针)进行++操作,因此它可以应用于某些ForwardIterator
,例如链表的迭代器。其他提示?
最佳答案
就这两种算法的基本思想而言,都是正确的。他们将进行相同次数的比较,但第二个将比第一个进行更多的交换。
您可以通过逐步执行算法来看到这一点,因为它们使用 5 作为主元对数组 1 9 2 8 3 7 4 6 5
进行分区。当第一个算法交换两个数字时,它再也不会触及其中任何一个。第二种算法首先交换 9 和 2,然后交换 9 和 3,依此类推,通过多次交换将 9 移动到最终位置。
还有其他差异。如果我没有犯任何错误,这就是第一个算法对数组进行分区的方式:
1 9 2 8 3 7 4 6 5
f l
1 9 2 8 3 7 4 6 5 # swap 9,5
f l
1 5 2 8 3 7 4 6 9 # swap 8,4
f l
1 5 2 4 3 7 8 6 9 # return f = 5
l f
这是第二个算法对数组进行分区的方式:
1 9 2 8 3 7 4 6 5 # 1<5, swap 1,1
bi
1 9 2 8 3 7 4 6 5 # 9>5, no swap
bi
1 9 2 8 3 7 4 6 5 # 2<5, swap 9,2
b i
1 2 9 8 3 7 4 6 5 # 8>5, no swap
b i
1 2 9 8 3 7 4 6 5 # 3<5, swap 9,3
b i
1 2 3 8 9 7 4 6 5 # 7>5, no swap
b i
1 2 3 8 9 7 4 6 5 # 4<5, swap 8,4
b i
1 2 3 4 9 7 8 6 5 # 6>5, no swap
b i
1 2 3 4 9 7 8 6 5 # 5=5, exit loop, swap 9,5
b i
1 2 3 4 5 7 8 6 9 # return b = 4
b i
请注意它如何进行 5 次交换,而其他算法仅进行 2 次。它还将数组中的最后一项移动到中间数组。在这种情况下,最后一项恰好是枢轴,因此枢轴移动到了中间,但这不是一般情况。
关于c++ - 快速排序中使用的两个版本的分区的差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18889110/