2015-07-14 09:39 已编辑

关注

C++ 之高效使用STL(排序算法的选择 )

当很多程序员想到排序对象时，只有一个算法出现在脑海： sort 。（有些程序员想到 qsort ，但一旦他们看了条款 46 ，他们会放弃 qsort 的想法并用 sort 的想法取代之。）

现在， sort 是一个令人称赞的算法，但如果你不需要你就没有必要浪费表情。有时候你不需要完全排序。比如，如果你有一个 Widget 的 vector ，你想选择 20 个质量最高的 Widget 发送给你最忠实的客户，你需要做的只是排序以鉴别出 20 个最好的 Widget ，剩下的可以保持无序。你需要的是部分排序，有一个算法叫做 partial_sort ，它能准确地完成它的名字所透露的事情：

bool qualityCompare(const Widget& lhs, const Widget& rhs)

{

// 返回 lhs 的质量是不是比 rhs 的质量好

}

...

partial_sort(widgets.begin(),// 把最好的 20 个元素

widgets.begin() + 20, // （按顺序）放在 widgets 的前端

widgets.end(),

qualityCompare);

// 使用 widgets...

调用完 partial_sort 后， widgets 的前 20 个元素是容器中最好的而且它们按顺序排列，也就是，质量最高的 Widget 是 widgets[0] ，第二高的是 widgets[1] 等。这就是你很容易把最好的 Widget 发送给你最好的客户，第二好的 Widget 给你第二好的客户等。

如果你关心的只是能把 20 个最好的 Widget 给你的 20 个最好的客户，但你不关心哪个 Widget 给哪个客户， partial_sort 就给了你多于需要的东西。在那种情况下，你需要的只是任意顺序的 20 个最好的 Widget 。 STL 有一个算法精确的完成了你需要的，虽然名字不大可能从你的脑中迸出。它叫做 nth_element 。

nth_element 排序一个区间，在 ri 位置（你指定的）的元素是如果区间被完全排序后会出现在那儿的元素。另外，当 nth_element 返回时，在 n 以上的元素没有在排序顺序上在位置 n 的元素之后的，而且在 n 以下的元素没有在排序顺序上在位置 n 的元素之前的。如果这听起来很复杂，那只是因为我必须仔细地选择我的语言。一会儿我会解释为什么，但首先让我们看看怎么使用 nth_element 来保证最好的 20 个 Widget 在 widgets vector 的前端：

nth_element(widgets.begin(),// 把最好的 20 个元素

widgets.begin() + 19, // 放在 widgets 前端，

widgets.end(),// 但不用担心

qualityCompare); // 它们的顺序

正如你所见，调用 nth_element 本质上等价于调用 partial_sort 。它们结果的唯一区别是 partial_sort 排序了在位置 1-20 的元素，而 nth_element 不。但是两个算法都把 20 个质量最高的 Widget 移动到 vector 前端。

那引出一个重要的问题。当有元素有同样质量的时候这些算法怎么办？比如假设有 12 个元素质量是 1 级（可能是最好的）， 15 个元素质量是 2 级（第二好的）。在这种情况下，选择 20 个最好的 Widget 就是选择 12 个 1 级的和 15 个中的 8 个 2 级的。 partial_sort 和 nth_element 怎么判断 15 个中的哪些要放到最好的 20 个中？对于这个问题，当多个元素有等价的值时 sort 怎么判断元素的顺序？

partial_sort 和 nth_element 以任何它们喜欢的方式排序值等价的元素，而且你不能控制它们在这方面行为。（条款 19 可以告诉你什么是两个值等价。）在我们的例子中，当需要把质量都是 2 级的 Widget 选出最后 8 个放到 vector 的前 20 个时，它们可以选择它们想要的任何一个。这不是没有理由的。如果你需要 20 个最好的 Widget 和一些也很好的 Widget ，你不该抱怨你取回的 20 个至少和你没有取回的一样好。

对于完整的排序，你有稍微多一些的控制权。有些排序算法是稳定的。在稳定排序中，如果一个区间中的两个元素有等价的值，它们的相对位置在排序后不改变。因此，如果在（未排序的） widgets vector 中 Widget A 在 Widget B 之前，而且两者都有相同的质量等级，那么稳定排序算***保证在这个 vector 排序后， Widget A 仍然在 Widget B 之前。不稳定的算法没做这个保证。

partial_sort 是不稳定的。 nth_element 、 sort 也没有提供稳定性，但是有一个算法 ——stable_sort—— 它完成了它的名字所透露的。如果当你排序的时候你需要稳定性，你可能要使用 stable_sort 。 STL 并不包含 partial_sort 和 nth_element 的稳定版本。

现在谈谈 nth_element ，这个名字奇怪的算法是个引人注目的多面手。除了能帮你找到区间顶部的 n 个元素，它也可以用于找到区间的中值或者找到在指定百分点的元素：

vector<Widget>::iterator begin(widgets.begin());// 方便地表示 widgets 的

vector<Widget>::iterator end(widgets.end()); // 起点和终点

// 迭代器的变量

vector<Widget>::iterator goalPosition; // 这个迭代器指示了

// 下面代码要找的

// 中等质量等级的 Widget

// 的位置

goalPosition = begin + widgets.size() / 2; // 兴趣的 Widget

// 会是有序的 vector 的中间

nth_element(begin, goalPosition, end, // 找到 widgets 中中等

qualityCompare); // 质量等级的值

... // goalPosition 现在指向

// 中等质量等级的 Widget

// 下面的代码能找到

// 质量等级为 75% 的 Widget

vector<Widget>::size_type goalOffset = // 指出兴趣的 Widget

0.25 * widgets.size(); // 离开始有多远

nth_element(begin, begin + goalOffset, end, // 找到质量值为

qualityCompare); // 75% 的 Widget

... // begin + goalOffset 现在指向

// 质量等级为 75% 的 Widget

如果你真的需要把东西按顺序放置， sort 、 stable_sort 和 partial_sort 都很优秀，当你需要鉴别出顶部的 n 个元素或在一个指定位置的元素时 nth_element 就会买单。但有时候你需要类似 nth_element 的东西，但不是完全相同。比如假设，你不需要鉴别出 20 个质量最高的 Widget 。取而代之的是，你需要鉴别出所有质量等级为 1 或 2 的。当然你可以按照质量排序这个 vector ，然后搜索第一个质量等级比 2 差的。那就可以鉴别出质量差的 Widget 的区间起点。

但是完全排序需要很多工作，而且对于这个任务做了很多不必要的工作。一个更好的策略是使用 partition 算法，它重排区间中的元素以使所有满足某个标准的元素都在区间的开头。

比如，移动所有质量等级为 2 或更好的 Widget 到 widgets 前端，我们定义了一个函数来鉴别哪个 Widget 是这个级别。

bool hasAcceptableQuality(const Widget& w)

{

// 返回 w 质量等级是否是 2 或更高 ;

}

传这个函数给 partition ：

vector<Widget>::iterator goodEnd =// 把所有满足 hasAcceptableQuality

partition(widgets.begin(),// 的 widgets 移动到 widgets 前端，

widgets.end(),// 并且返回一个指向第一个

hasAcceptableQuality); // 不满足的 widget 的迭代器

此调用完成后，从 widgets.begin() 到 goodEnd 的区间容纳了所有质量是 1 或 2 的 Widget ，从 goodEnd 到 widgets.end() 的区间包含了所有质量等级更低的 Widget 。如果在分割时保持同样质量等级的 Widget 的相对位置很重要，我们自然会用 stable_partition 来代替 partition 。

算法 sort 、 stable_sort 、 partial_sort 和 nth_element 需要随机访问迭代器，所以它们可能只能用于 vector 、 string 、 deque 和数组。对标准关联容器排序元素没有意义，因为这样的容器使用它们的比较函数来在任何时候保持有序。唯一我们可能会但不能使用 sort 、 stable_sort 、 partial_sort 或 nth_element 的容器是 list ， list 通过提供 sort 成员函数做了一些补偿。（有趣的是， list::sort 提供了稳定排序。）所以，如果你想要排序一个 list ，你可以，但如果你想要对 list 中的对象进行 partial_sort 或 nth_element ，你必须间接完成。一个间接的方法是把元素拷贝到一个支持随机访问迭代器的容器中，然后对它应用需要的算法。另一个方法是建立一个 list::iterator 的容器，对那个容器使用算法，然后通过迭代器访问 list 元素。第三种方法是使用有序的迭代器容器的信息来迭代地把 list 的元素接合到你想让它们所处的位置。正如你所见，有很多选择。

partition 和 stable_partition 与 sort 、 stable_sort 、 partial_sort 和 nth_element 不同，它们只需要双向迭代器。因此你可以在任何标准序列迭代器上使用 partition 和 stable_partition 。

我们总结一下你的排序选择：

如果你需要在 vector 、 string 、 deque 或数组上进行完全排序，你可以使用 sort 或 stable_sort 。
如果你有一个 vector 、 string 、 deque 或数组，你只需要排序前 n 个元素，应该用 partial_sort 。
如果你有一个 vector 、 string 、 deque 或数组，你需要鉴别出第 n 个元素或你需要鉴别出最前的 n 个元素，而不用知道它们的顺序， nth_element 是你应该注意和调用的。
如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准，你大概就要找 partition 或 stable_partition 。
如果你的数据是在 list 中，你可以直接使用 partition 和 stable_partition ，你可以使用 list 的 sort 来代替 sort 和 stable_sort 。如果你需要 partial_sort 或 nth_element 提供的效果，你就必须间接完成这个任务，但正如我在上面勾画的，会有很多选择。

另外，你可以通过把数据放在标准关联容器中的方法以保持在任何时候东西都有序。你也可能会考虑标准非 STL 容器 priority_queue ，它也可以总是保持它的元素有序。（ priority_queue 在传统上被考虑为 STL 的一部分，但是，正如我在导言中提到的，我对 “STL” 的定义是要求 STL 容器支持迭代器，而 priority_queue 并没有迭代器。）