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的例子：

#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容器中的元素进行排序。最终输出的结果是一个有序序列。