插入排序的正确性证明 以及各种改进方法
插入排序概述 最符合人类思维的简单排序算法 1 3 4 6 7 5 2 1 3 4 5 6 7 2 1 2 3 4 5 6 7 1 3 4 6 7 5 2 1 3 4 5 6 7 2 每一个外循环是将A[i]插入位置,内循环腾出位置 1 2 3 4 5 6 7
j (1) 1 3 4 5 6 7 2 X=2 (2) 1 3 4 5 6 7 7 1 3 4 5 6 6 7 (3) 1 3 4 5 5 6 7 1 3 4 4 5 6 7 1 3 3 4 5 6 7 (4) 1 2 3 4 5 6 7
(1) (2) (3) (4)
(1) (2) (3) (4)
插入排序的效率? 非递归排序算法:冒泡排序、选择排序 < 插入排序 递归算法:归并排序,快速排序 影响插入排序效率的主要因素: 1、比较大小 O(n^2) 2、数组元素移动 O(n^2) → ?
减少比较次数 内循环二分查找 1 3 4 5 6 7 2 O(n^2)+O(nlogn)
减少移动次数 考虑链表 支持快速访问元素的链表? 1 → 3 → 4 → 5 → 6 → 7 2 O(n)+O(n^2)
跳跃表 skip list 5 ? ? ? 从最高层开始查找,依次下降 支持O(logn)查询 用跳跃表优化插入排序,时间复杂度可以和归并和快排媲美
谢尔排序 玄学优化? 让元素交换大步跳跃! 一个好的跳跃序列的选取,决定了谢尔排序的速度 可以达到O(n(logn)^2)甚至更好