排序算法 – LOFFER – 一个可以fork的博客

一. 衡量算法的好坏

衡量排序算法的好坏一般从这几个角度分析:

衡量算法的优劣首先离不开时间复杂度的分析, 另外对于不同规律的原始数据, 算法的性能表现也有不同. 例如乱序和完全有序的两组数据, 对执行时间也是有影响的.

稳定性也是取舍算法的一项重要指标. 所谓稳定性是说: 序列中若存在等值元素, 排序之后等值元素的相对位置不变.

例如: 4, 2(1), 3, 2(2), 6. (括号中用来表示不同的2). 若保证稳定性, 则排序后应为: 2(1), 2(2), 3, 4, 6. 即两个2的相对位置没有变化.

若算法可满足此特性, 则称之为稳定性的排序算法, 反之则称为不稳定的排序算法.

3.1 上面的例子可以理解稳定性的概念, 那么实际的应用中稳定性有什么意义呢?

在实际的开发中, 单纯地比较数字大小的情况较少, 多数情况是提供一组对象, 根据对象的某些字段进行排序. 例如: User(Integer id, Integer age) 对象. 假如定义这样的排序规则: 根据 age 升序, 当 age 相同时按 id 降序. 原始数据如下:

  id
  age

  :

bigwolftime / gitmentCommentsPlugin