阅读量:6
stable_sort是C++标准库中提供的一种排序算法，它能够对一个容器中的元素进行排序，并保持相等元素的相对位置不变，也就是说，如果两个元素在排序前是相等的，那么在排序后它们仍然是相等的。
stable_sort的时间复杂度为O(NlogN)，其中N为容器中元素的个数。它采用的是一种分治法的思想，首先将容器分为两个子序列，然后对每个子序列进行排序，最后再将两个子序列合并起来。在合并的过程中，如果两个元素相等，那么会优先选择原来在前面的元素，这样就能够保持相等元素的相对位置不变。
在具体实现上，stable_sort通常使用归并排序（merge sort）算法。归并排序将容器不断二分，直到每个子序列只有一个元素，然后再将这些子序列两两合并，直到得到最终的有序序列。在合并的过程中，需要使用额外的内存空间来存储临时结果。
使用stable_sort需要包含
template
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
其中，first和last分别表示容器中要排序的元素的起始和结束位置，它们应该是随机访问迭代器。stable_sort会对[first, last)范围内的元素进行排序。
下面是一个使用stable_sort的例子：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6}; std::stable_sort(nums.begin(), nums.end()); for(int num : nums) { std::cout << num << " "; } std::cout << std::endl; return 0; } 输出结果为：1 2 3 4 5 6 7 8 9
这个例子中，我们使用stable_sort对一个vector容器中的元素进行排序。最终输出的结果是一个有序序列。
