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