2

The first one is straightforward, just walk from both sides until finding a reversion.

/*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;
    }
}

The second one (shown in "Introduction to algorithms") is:

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;
}

The invariant of the second one is " All elements before bound is less than pivot " .

Q: And what is the advantages and disadvantages of the two versions?

I'll give one first, the second one require ++ operation on the iterator( pointer ), so it can be applied to some ForwardIterator like the iterator of a linked list. Other tips?

4

1 回答 1

3

就这两种算法的基本思想而言，两者都是正确的。他们将进行相同数量的比较，但第二个将比第一个进行更多的交换。

您可以通过逐步执行算法来查看这一点，因为它们1 9 2 8 3 7 4 6 5使用 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 次。它还将数组中的最后一项移动到中间数组。在这种情况下，最后一项恰好是枢轴，所以它是移动到中间的枢轴，但这不是一般情况。

于 2013-09-19T08:47:52.573 回答