C++ stable_sort(STL stable_sort)排序算法详解

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的例子：
```cpp
#include
#include
#include
int main() {
std::vector 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容器中的元素进行排序。终究输出的结果是一个有序序列。