总目录

stable_sort

当我们翻阅STL所有的算法函数时，我们会看到两对这样的函数名称：

• sort—stable_sort
• partition—stable_partition

他们的名字只有一词只差，区别到底在哪里呢，我们这次先来看看第一组：sort—stable_sort
先来复习一下小学英语

stable
adj. 稳定的;稳固的;牢固的;稳重的;沉稳的;持重的;(化学状态或原子状态)稳定的

那stable_sort就是一个稳定的sort喽，所以stable_sort的用法与sort也基本相同，这里不再赘述( 不会sort的同学看过来 )
接下来，我们再来回顾一下什么是稳定排序，什么是不稳定排序：

稳定排序：排序前后两个相等的数相对位置不变，则算法稳定
非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定

常用的排序算法中，根据 排序算法的实现原理 ，我们可以以稳定性对它们分类：

• 稳定排序：冒泡排序，插入排序，归并排序（stable_sort的基本原理），基数排序
• 不稳定排序：快速排序（sort的基本原理），选择排序，shell希尔排序，堆排序

比如对于1 2 3 4 2这样一组数据，当我们使用不稳定排序算法进行排序时，不稳定排序算法不能保证两个2的先后顺序是否与输入时得顺序相同，虽然两个函数排序后的结果都是1 2 2 3 4，但两个2的先后顺序却不一定相同，这一问题在一些特殊情况下会对程序的最终结果产生一些影响，但如果只是简单的进行数字的排序，那么稳定性将毫无意义。
在时间复杂度方面，由于stable_sort原理是归并排序而sort是快速排序，所以stable_sort可能会稍稍慢那么一内内，但相差无几，所以基本不需要担心超时问题。