7、排序 - 《数据结构和算法》

比较排序算法的执行效率

一般需要排序的数据规模不会很大，比如10个，100个，1000的，所以我们需要考虑到系数、常数、低阶

原地排序：特质空间复杂度为O(1)的排序算法
冒泡、插入、选择都是原地排序算法

4.1、概念：如果待排序的序列中存在值相等的元素，经过排序之后，相当元素之间原有的先后顺序不变

4.2、举例：我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。