c++ sort()是稳定排序吗?

Question

如题所述

Answer 1

　　c++sort不是稳定排序，stl中stable_sort才是稳定排序。
　　稳定排序的概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

Answer 2

sort不是稳定排序。stl中stable_sort才是稳定排序。

稳定排序的概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。本回答被提问者和网友采纳

Answer 3

C++中的sort()不是稳定排序。
因为当数据量稍大时，sort()就会使用快速排序，而快速排序是不稳定排序，即不能保证原序列中相等的元素在排序后保持相对位置不变。
在C++中若要进行稳定排序，可使用STL的stable_sort()。

Answer 4

sort()内部实现的方式是内省式排序，本质上是快排，插排和堆排的的结合，进入函数后先检验分割后各部分的元素数，若发现分割方式有退化为二次的风险是改用堆排，再判断快排分割层次，若分割层次过多，则改为堆排，最后进入快排，当分割出来的数据长度小于一定阀值时，再用插排完成最后的排序。也就是说，sort()本质上是一种快排，是不稳定排序。
参考资料：
STL sort 函数内部的实现 为什么会比你写的快...：http://blog.sina.com.cn/s/blog_9d987af501014zlj.html