知识卡片
稳定排序保留同键先后
若两个记录在比较键上相等,稳定排序保证它们在输出中的先后与输入一致。不稳定排序只是没有这个保证,某次输出仍可能碰巧保持顺序。
03183先按起飞时间排列,再稳定按目的地排序;同一目的地组内保留先前的时间顺序。此技巧要求第一次顺序和第二次比较键明确,若需要按更多字段排序还要定义相应优先级。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
相对顺序也许是很重要的,也就是说,如果i<j,那么ai的最终位置必须在aj的最终位置的左边。能够保证这种性质的排序算法都被认为是稳定的。例如,在图4-4的顶部表示了一个已经按照当天航班时间(忽略航线或者目的地这两个参数)排好序的航班信息集合A。如果A使用一个排序函数(cmpDestination)按
参考来源
- 位置:《算法技术手册》第4章《稳定排序》(spine1494;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1457.html;u064-ch04-005)。
- 结论依据:64全文及03183前后完整航班表实读。
- 原始内容:相对顺序也许是很重要的,也就是说,如果i<j,那么ai的最终位置必须在aj的最终位置的左边。能够保证这种性质的排序算法都被认为是稳定的。例如,在图4-4的顶部表示了一个已经按照当天航班时间(忽略航线或者目的地这两个参数)排好序的航班信息集合A。如果A使用一个排序函数(cmpDestination)按