学习C++STL中的stable_sort算法

排序是计算机科学中最基本也是最常见的算法之一。在C++的标准模板库中，STL提供了一系列的排序算法，其中包括了stable_sort。

什么是stable_sort

stable_sort可以对一个数组或容器中的元素进行排序，它与普通的sort算法一样，都采用了快速排序的算法，所以时间复杂度都为O(nlog(n))。但是它与普通的sort不同的是，stable_sort是稳定排序。所谓稳定排序是指如果两个元素的键值相等，排序后两个元素的相对顺序与排序之前相同。

使用stable_sort

在使用stable_sort之前，我们需要了解它的调用方式以及如何使用它进行排序。在C++标准库中，stable_sort算法的定义如下:

template<classRandomIt>
voidstable_sort(RandomItfirst,RandomItlast);

其中，RandomIt代表任意一个指针类型，比如数组的指针或者容器的迭代器。调用stable_sort的方式非常简单，只需要传入需要进行排序的数组、容器的首指针和尾指针，stable_sort会自动进行排序。例如：

inta[]={3,1,4,1,5,9,2,6};
std::vector<int>vec(a,a+8);
std::stable_sort(a,a+8);
std::stable_sort(vec.begin(),vec.end());

其中我们用一个数组和一个STL中的vector容器来演示stable_sort如何进行排序。演示代码可以看到，stable_sort的调用非常简单，只需要传入容器或者数组的首指针和尾指针即可。

稳定排序的例子

为了更好地理解stable_sort的稳定性，我们来看一个具体的例子：

structStudent{
std::stringname;
intscore;
};
boolcompare(constStudent&a,constStudent&b)
{
if(a.score!=b.score)
returna.score<b.score;
else
returna.name<b.name;
}
intmain()
{
Studenta[4]={{\"Jack\",85},{\"Tom\",90},{\"Jerry\",90},{\"Mary\",85}};
std::stable_sort(a,a+4,compare);
for(inti=0;i<4;++i){
std::cout<<a[i].name<<\":\"<<a[i].score<<std::endl;
}
return0;
}

在这个例子中，我们使用了一个学生结构体数组，学生的成绩和名字都是考试时随机生成的。我们希望按照成绩从小到大排序，如果有两个学生的成绩相等，那么按照名字的字典序进行排序。这个时候我们肯定希望排序后相等成绩的学生的相对排名不变。

在调用stable_sort后，程序输出结果如下：

Jack:85
Mary:85
Jerry:90
Tom:90

在这个例子中，我们固定了学生的成绩和姓名，以达到对比排序前后成绩相等的学生对应的名字。可以看到，排序后成绩相等的两位学生Jack和Mary的相对顺序没有改变，这说明stable_sort真的是稳定排序，符合我们对于稳定性的定义。

结论

stable_sort对于一些特殊情况下的排序非常有用。例如，在某些情况下我们要对成绩相等的学生进行排序，这个时候stable_sort比sort更多的符合我们的预期。stable_sort和sort的使用方式非常相似，只是稳定与否的区别需要我们在使用的时候特别注意。