如何分析排序算法？ #

1. 最好情况、最坏情况、平均情况时间复杂度

2. 时间复杂度的系数、常数 、低阶

3. 比较次数和交换（或移动）次数

排序算法的内存消耗 #

内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性 #

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

在排序的时候都是用整数来举例，但在真正软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个 key 来排序。比如按照订单的金额来排序，金额相同的订单，我们希望按照下单时间先后来排序，这样就需要稳定排序算法来保证金额相同的订单，下单时间靠前的在前面。

分析 #

1. 冒泡排序

   是原地排序，因为值涉及相邻数据的交换操作

   是稳定的排序，因为相邻元素大小相等时不会交换所以顺序不会改变

   时间复杂度，假设要从头到尾都发生了交换那么复杂度为 O(n2次)，如果数组已经有序则为 O(n)

2. 插入排序

   是原地排序，不需要额外的存储空间

   是稳定的排序，对于相同的元素，可以将后面出现的插入前面元素的后面

   复杂度O(n2次)