糊秃秃

分类

题解(5)

/ 注册

全部文章（共2篇）

插入排序

插入排序过程中，序列分为已遍历部分和未遍历部分，已遍历序列有序，未遍历序列有序性未知，为了做到这一点，在每遍历每一个数时O(n)，依次在已遍历序列中从后往前比较O(n)，将当前数放入适当位置，直至未遍历部分为空O(n ^ 2)。相当于摸牌将牌组分为，手中的牌和牌组中的牌，手中的牌有序，牌组中的牌有序...

剑指offer 快速排序 insert

2019-08-23

4 1242

快速排序

快速排序也是使用分治策略，用partition函数将序列一分为二(O(n))后，将子序列递归排序((1 / n) * ∑[T(k) + T(n - k - 1)])，最后合并有序子序列(O(1))，T(n) = O(n) + (1 / n) * ∑[T(k) + T(n - k - 1)] = O(...

剑指offer 快速排序 partition

2019-08-22

3 1478