stable_sort.md

#稳定排序（std::stable_sort）

定义于头文件<algorithm>中：

template< typename RandomIt >
void stable_sort( RandomIt first, RandomIt last );    (1)

template< typename randomIt, typename Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );       (2)

升序排序区间[first, last)里的元素，注意不包括last所指向的元素，同时保证相等元素的先后顺序不变，即稳定排序。版本(1)用<排序，即默认为升序，版本(2)用自定义的函数cmp。

##参数

first, last —— 待排序的元素的区间

comp —— 比较函数，若第一个参数小于第二个则返回true。 比较函数必须使用下面的等效声明：

bool cmp(const Type1 &a, const Type2 &b);

比较函数不一定非得声明为const &，但是这个函数对象应该不能修改传递过来的参数。

类型Type1和Type2必须是能够解除引用操作和隐式互转的RandomIt类型。

类型约束

• RandomIt必须满足值可交换和随机访问迭代器的要求。
• 解除引用的RandomIt类型必须满足可移动和可移动构造。

##返回值 无返回值。

##复杂度

O(Nlog^2(N)), 其中N = std::distance(first, last)为比较次数。若能够使用额外空间，则复杂度会降为O(Nlog(N))。

##注意

该函数会先尝试分配等同于待排序列长度大小的临时缓冲区，通常通过调用库函数std::get_temporary_buffer来实现。如果空间分配失败，将会选择低效的版本。

##例子

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

struct Employee {
    Employee(int age, std::string name) : age(age), name(name) { }
    int age;
    std::string name;  // Does not particpate in comparisons
};

bool operator<(const Employee &lhs, const Employee &rhs) {
    return lhs.age < rhs.age;
}

int main()
{
    std::vector<Employee> v = {
        Employee(108, "Zaphod"),
        Employee(32, "Arthur"),
        Employee(108, "Ford"),
    };

    std::stable_sort(v.begin(), v.end());

    for (const Employee &e : v) {
        std::cout << e.age << ", " << e.name << '\n';
    }
}

输出为：

32, Arthur
108, Zaphod
108, Ford

##另见

• partial_sort 按一定顺序排出区间里的前N个元素（函数模板）（函数模板）
• sort 递增排序，且不一定会保持相等元素的先后次序（函数模板）（函数模板）