活跃农民
- 积分
- 499
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-10-7
- 最后登录
- 1970-1-1
|
本帖最后由 gongluan 于 2012-12-1 16:13 编辑
用 3-Way Partitioning 算法解决,只需要扫描一遍元素,时间复杂度 O(n),代码如下
- #include <iostream>
- #include <vector>
- #include <list>
- #include <iterator>
- #include <algorithm>
- using namespace std;
- /*
- * 3-Way Partitionion Algorithm
- *
- * See the following materials for more information.
- *
- * http://en.wikipedia.org/wiki/Dutch_national_flag_problem
- * http://www.sorting-algorithms.com/quick-sort-3-way
- * Algorithms, 4th Edition, by Robert Sedgewick & Kevin Wayne, p298
- */
- template <typename BidirectionalIterator>
- pair<BidirectionalIterator, BidirectionalIterator>
- three_way_partition(BidirectionalIterator first, BidirectionalIterator last)
- {
- if (first == last)
- return make_pair(first, first);
- /*
- * +---+---------+---------+---------+---------+
- * | | < | = | ? | > |
- * +---+---------+---------+---------+---------+
- * ^ ^ ^ ^
- * | | | |
- * pivot lt iter gt
- */
- BidirectionalIterator pivot = first;
- BidirectionalIterator lt = ++first;
- BidirectionalIterator iter = lt;
- BidirectionalIterator gt = last;
- // Loop through the list and move each element to the right part
- // according to its value compared to the pivot element.
- while (iter != gt) {
- if (*iter < *pivot) // less than pivot, move left
- swap(*iter++, *lt++);
- else if (*iter > *pivot) // greater than pivot, move right
- swap(*iter, *--gt);
- else // equal to pivot, leave it there
- ++iter;
- }
- // Move the pivot element to the right position
- swap(*pivot, *--lt);
- // Return a pair of iterators pointing to the middle part of the list
- return make_pair(lt, iter);
- }
- int main()
- {
- // 初始时往 vector 里放入一个 1,作为 pivot element
- // vector<int> vec(1, 1);
- list<int> lst(1, 1);
- // 然后往 vector 里面填充 n 个 [0,1,2] 之间的数
- srand(time(NULL));
- const size_t num_elements = 20;
- for (size_t i = 0; i < num_elements; ++i)
- lst.push_back(rand() % 3);
- // 执行 3-way-partion
- three_way_partition(lst.begin(), lst.end());
- // 输出结果
- copy(lst.begin(), lst.end(), ostream_iterator<int>(cout, " "));
- cout << endl;
- return 0;
- }
复制代码 |
|