插入排序的正确性证明以及各种改进方法.

插入排序的正确性证明以及各种改进方法

插入排序概述最符合人类思维的简单排序算法 1 3 4 6 7 5 2 1 3 4 5 6 7 2 1 2 3 4 5 6 7
每一个外循环是将A[i]插入位置，内循环腾出位置

j （1） X=2 （2）（3）（4）

（1）（2）（3）（4）

插入排序的效率？非递归排序算法：冒泡排序、选择排序 < 插入排序递归算法：归并排序，快速排序影响插入排序效率的主要因素：
1、比较大小 O(n^2) 2、数组元素移动 O(n^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)甚至更好

Presentation on theme: "插入排序的正确性证明以及各种改进方法."— Presentation transcript: