什么是稳定的排序算法,举个简单的例子,对四张扑克牌按照牌面值进行升序排序,对于红桃5和黑桃5,牌面值相同,如果使用稳定的排序算法,则排序前是红桃5在前、黑桃5在后的相对顺序,在排序后依然是这个顺序。
如果使用不稳定的排序算法,则红桃5和黑桃5的相对顺序被打乱。
稳定的排序算法有什么作用?
再举个查询学生情况的例子,
先按照年龄升序排序从数据库中查出前四条记录:
学生姓名 |
年龄↑ |
成绩 |
王五 |
9 |
98 |
小明 |
10 |
91 |
张三 |
11 |
80 |
李四 |
11 |
91 |
再点击“成绩”这列,通过前端JavaScript进行升序排序,稳定排序的结果如下图所示:
学生姓名 |
年龄 |
成绩↑ |
张三 |
11 |
80 |
小明 |
10 |
91 |
李四 |
11 |
91 |
王五 |
9 |
98 |
可以发现之前按照年龄升序排列的小明依旧在前,李四在后。这个也是我们希望看到的合理的结果。
另外,具备稳定性的排序算法的主要作用是有利于基数排序的实现,关于基数排序,可参考:
http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html
参考资料:
http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
相关推荐
小排序算法的稳定性和时间复杂度
各种排序算法的稳定性和时间复杂度总结。希望大家能有所收获。
排序算法的稳定性排序算法的稳定性排序算法的稳定性
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
常用排序算法的比较 复杂度 稳定性 shell 归并排序 插入排序 冒泡排序 快速排序 基数排序
Python 算法 06排序算法的稳定性.mp4
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,...还可以对稳定性作验证。
各种排序算法的稳定性和时间复杂度小结,包含各种排序算法,对找工作,做项目都有帮助
每种排序的效率、稳定性和算法的复杂程度都有所区别。在实际应用中,插入排序和现则排序因为实现简单,使用的比较多,但是在对效率要求比较高、且待排序数据量大的场合,还是应该采用时间复杂度较低的排序算法,因此...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 (1)对起泡排序、直接排序、简单选择排序、快速排序...(2)验证各算法的稳定性; (3)输出界面的优化。(柱长or曲线表示所用时间)
排序算法是数据结构与算法中最基本的算法之一。 排序算法可以分为内部排序和...关于稳定性: 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
[问题描述] 设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 [需求分析] (1)对起泡排序、直接排序、简单选择排序、快速排序、希尔...(2)验证各算法的稳定性; (3)输出界面的优化。
各种排序算法的稳定性和时间复杂度小结.pdf
各种排序算法的稳定性和时间复杂度小结.doc
快速排序 归并排序 希尔排序掌握常用的排序方法,并掌握用高级语言实现排序算法的方法; 深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用; 了解各种方法的排序过程及其依据的原则,并掌握各种排序方法...
⑶ 评价排序的指标有:在表长相同的情况下,各种排序算法的关键字比较次数、关键字移动次数(关键字交换记为3次移动)、排序时间、排序算法的稳定性;当改变表长时,各种排序算法的性能变化情况, ⑷ 结果记录及分析...
其次,利用Score结构体数组讨论排序算法的稳定性。 最后,对double型数组的3个排序函数进行修改,在每个函数中增加2个无符号扩展的长整型指针形参(unsigned long long *),分别用于间接“返回”相关函数执行数组...