算法 - 如何分析排序算法

• 极客时间 - 数据结构与算法之美 - 11 | 排序（上）

执行效率

• 最好、最坏、平均时间复杂度
• 时间复杂度的系数、常数、低阶
• 比较次数、交换（或移动）次数

空间复杂度

• 原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

有序度分析

有序度：有序元素对：a[i] <= a[j]，如果 i < j 的数量

满序度：

• 完全有序的数组的有序度
• 对于长度为n的数组，满序度 = n * (n - 1) / 2
• 举例：长度6的数组，满序度 = 6 * (6 - 1) / 2 = 15

逆序度：逆序度 = 满序度 - 有序度