最近在看算法,书上关于稳定性的概念一带而过,甚觉不爽,于是网上搜了个貌似靠谱的答案。答案来自stackoverfollow
问:
I m very curious, why stability is or is not important in sorting algorithms?
Any ideas?
靠谱的答:
Background: a "stable" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:
peach straw apple spork
Stable-sorting by the first letter gives us:
apple peach straw spork
In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since 'straw' appears before 'spork' in the input, it also appears before 'spork' in the output).
We could sort the list of words using this algorithm: stable sorting by column 5, then 4, then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (by the way, that algorithm is called radix sort)
Now to answer your question, suppose we have a list of first and last names. We are asked to sort "by last name, then by first". We could first stable sort by the first name, then sort by the last name. After these sorts, the list is primarily sorted by the last name. However, where last names are the same, the first names are sorted.
You can't stack unstable sorts in the same fashion
分享到:
相关推荐
误差传播与算法稳定性matlab程序,经过测试,比较稳定。
误差传播与算法稳定性实验报告(1).doc
算法稳定性MATLAB.exe
视频监控中人脸识别算法稳定性的改进.pdf
基于KVM的虚拟机Post-Copy动态迁移算法稳定性优化.docx
协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定性研究.pdf协同过滤推荐算法稳定...
协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐算法稳定性研究.docx协同过滤推荐...
距离保护的仿真研究及其算法稳定性分析 距离保护的仿真研究及其算法稳定性分析距离保护的仿真研究及其算法稳定性分析
误差传播与算法稳定性实验报告.doc
一种改进的粒子群算法稳定性证明及其应用.pdf
大数据-算法-三维MPS算法稳定性研究及在超声速雾化过程一体化模拟中的应用.pdf
ZXZ显式积分算法稳定性的数值模拟研究,张晓志,李根,在瑞雷阻尼假定下,以设定结构体系动力响应的数值模拟为主,理论分析为辅,并结合与PJ算法以及LL算法的对比分析,研究了ZXZ直接显�
试验一误差传播与算法稳定性一试验内容考虑一个简单由积分定义.pdf
小排序算法的稳定性和时间复杂度
实验一:误差传播与算法稳定性 一:实验内容 考虑一个简单由积分定义.doc
对该模型平衡点存在的条件和系统的稳定性进行了分析,与传统的网络控制算法相比,该算法考虑到边界条件的限制,得出了系统存在唯一平衡点的条件。通过TCP/E-RED网络对该理论进行了验证,结果表明,对于一般网络结构...
#资源达人分享计划#
初学者应用matlab验证简单的算法的稳定性
排序算法的稳定性排序算法的稳定性排序算法的稳定性