如何分析一个排序算法

• 排序算法的执行效率
  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数交换（或移动）次数
• 排序算法的内存消耗
  • 原地排序，特指空间复杂度是 O（1）的排序算法
• 排序算法的稳定性
  • 如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，则此排序算法是稳定的

平均情况时间复杂度的计算

1. 有序度

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

     

   • 完全有序的数组的有序度叫做满有序度，n*(n-1)/2，如 1，2，3，4，5

2. 逆序度
   • 逆序度 = 满有序度 - 有序度

排序算法

O(n^2)：冒泡排序、插入排序、选择排序

O(nlogn)：归并排序、快速排序、堆排序

O(n)：桶排序、计数排序、基数排序

排序算法对比

Topological Sorting 拓扑排序