std::stable_sort 与sort 区别

std::stable_sort和std::sort是C++标准库中的两个排序算法，它们在排序元素时有一些区别。

1. std::sort是一种不稳定的排序算法，而std::stable_sort是一种稳定的排序算法。稳定排序算法意味着如果两个元素的值相等，它们在排序后的结果中的相对顺序将保持不变。而不稳定排序算法则没有这个保证。

2. std::sort的平均时间复杂度为O(nlogn)，std::stable_sort的平均时间复杂度为O(nlog^2n)。这是因为std::stable_sort需要保持相等元素的相对顺序，所以在排序过程中需要更多的操作。

3. std::sort使用的是快速排序算法或者堆排序算法，而std::stable_sort使用的是归并排序算法。快速排序和堆排序是原地排序算法，它们不需要额外的内存空间。而归并排序需要额外的内存空间来存储临时结果。

下面是一个使用std::sort和std::stable_sort的示例：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {5, 2, 8, 3, 1, 4};

    // 使用std::sort进行排序
    std::sort(nums.begin(), nums.end());
    std::cout << "使用std::sort排序后的结果：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 使用std::stable_sort进行排序
    std::stable_sort(nums.begin(), nums.end());
    std::cout << "使用std::stable_sort排序后的结果：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果：
使用std::sort排序后的结果：1 2 3 4 5 8
使用std::stable_sort排序后的结果：1 2 3 4 5 8