|
首页 > STL > C++常用算法
C++ sort()排序函数用法详解
C++ STL 标准库提供有很多实用的排序函数，如表 1 所示。通过调用它们，我们可以很轻松地实现对普通数组或者容器中指定范围内的元素进行排序。
表 1 C++ STL 排序函数
函数名
用法
sort (first, last)
对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。
stable_sort (first, last)
和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。
partial_sort (first, middle, last)
从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中。
partial_sort_copy (first, last, result_first, result_last)
从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。
is_sorted (first, last)
检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。
is_sorted_until (first, last)
和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。
void nth_element (first, nth, last)
找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。
对于表 1 中罗列的这些函数，本教程会一一进行讲解，这里先介绍 sort() 函数。
C++ sort()排序函数
C++ STL 标准库中的 sort() 函数，本质就是一个模板函数。正如表 1 中描述的，该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序，除此之外我们也可以选择标准库提供的其它排序规则（比如std::greater降序排序规则），甚至还可以自定义排序规则。
sort() 函数是基于快速排序实现的，有关快速排序的具体实现过程，感兴趣的读者可阅读《快速排序（QSort，快排）算法》一文。
需要注意的是，sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 sort() 函数：
容器支持的迭代器类型必须为随机访问迭代器。这意味着，sort() 只对 array、vector、deque 这 3 个容器提供支持。
如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持 |