为什么要分稳定排序和非稳定排序


稳定非稳定如何界定

原始数据,a2和a4的位置都是3。对于稳定排序来说,排序后的序列,a2一定还是在a4前面。但是对于非稳定排序来说,就不一定了,可能排完序之后,a4反而在a2的前面了。

哪些常用算法是稳定的,哪些是不稳定的呢?

冒泡和归并排序是稳定的,快排和选择排序是非稳定的。

思考:既然最后都是有序序列,为什么还要分稳定和非稳定的排序呢?

为什么要分稳定和非稳定呢?

看一个典型的场景:每次考试完成后,都会按照分数进行排序。分高的自然就是第一名。分数相同的同学怎么办呢?那就是按照上次的分数来分高低。上次分高的排在前面。

这个时候就应该用稳定排序,在上次排好序的序列上,再针对这次的分数进行排序。稳定排序的结果能保证这次相同分数的人,上次分高的在前面。

再比如一个班的同学,已经按照学号排好序了。现在要按照身高排序。如果是稳定排序排好之后,身高相同的同学,还是按照学号顺序的。

其实就是有两个排序关键字的时候,稳定排序可以让第一个关键字排序的结果服务于第二个关键字排序中数值相等的那些数。