排序

估计下界

求解排序算法CBA()都有一个下界(n*logn)

1. 冒泡排序

2. 插入排序

算法的思路可简要描述为：始终将整个序列视作并切分为两部分：有序的前缀， 无序的后缀；通过迭代，反复地将后缀的首元素转移至前缀中。
在任何时刻，相对于当前节点 e = S[r]，前缀S[0,r)总是已有序。

3. 选择排序

与插入排序类似， 该算法也将序列划分为无序前缀和有序后缀两部分；此外，还要求前缀不大于后缀。如此，每次只需从前缀中选出最大者，并作为最小元素转移至后缀中，即可使有序部分的范围不断扩张。
在任何时刻，后缀S(r, n)已经有序，且不小于前缀S[0, r]

归并排序