分析排序算法的方法

算法的执行效率

• 复杂度 (数据规模, 形式)
  • 最好, 及对应的数据是什么样的
  • 最坏…
  • 平均…
• 时间复杂度的系数, 常数, 低阶 (数据规模较小时需要考虑)
• 比较和交换 (或移动) 次数 (也需要考虑)
  • 基于比较的排序算法会有这两个操作

算法的内存消耗

• 空间复杂度
  • 原地排序

算法的稳定性

指相同值的顺序在排序前后是否发生变化.

• 稳定
• 非稳定

有序度与逆序度

指数组中具有有序关系的元素对的个数.

例

数组 [2, 4, 3, 1, 5, 6] 的有序度为11, 其中的有序元素对为:

• (2, 4), (2, 3), (2, 5), (2, 6)
• (4, 5), (4, 6), (3, 5), (3, 6)
• (1, 5), (1, 6), (5, 6)

数组 [6, 5, 4, 3, 2, 1] 的有序度为0.

数组 [1, 2, 3, 4, 5, 6] 的有序度为 , 这种数据的有序度称为满有序度.

逆序度 = 满有序度 - 有序度. 当初始有序度为0时, 要使数组有序, 就是使逆序度为0. 最好情况下, 不用交换, 最坏情况下, 逆序度为 , 那么平均情况下为 .