数据结构、排序算法、时间复杂度、

排序 类别 插入 排序

基本思 想 每次将一 个待排序 记录按其 关键字大 小插入到 前面已排 好的子序 列中

排序 算法 直接 插入 排序 空间：O(1)

复杂度分析

稳定性 稳定 适用于顺序与链式存储

排序特点

最好:表正序 比较n-1次,不移动 O(1) n n 时间 最坏:表逆序 比较 i=2i ,移动 i=2(i+1) O(n2) 平均:O(n2) 空间：O(1) 稳定 仅仅减少了比较元素，比较次数与待排序表初始状态无关

折半 插入 排序

O(nlog2n) 与初始状态无关 比较： O(n2) 与初始状态有关 时间 移动： 平均:O(n2) 时间复杂度依赖于增量序列的函数 O(n^1.3) 不稳定， 相等关键 字记录被 划分到不 同的子表 确定增量：通过比较第一趟排序结果与初始条件，找第一个变续 的关键字，再与该关键字原位置对比确定增量

希尔 排序

交换 排序

根据序列 中两个元 素关键字 的比较结 果来对换 这两个记 录在序列 中的位置

冒泡 排序

空间 O(1)

稳定，相 邻比较相 等不换位

1) 2)

用 flag 控制比较次数：若有 flag,则比较次数与初始条件有 关；若没有 flag,则比较次数与初始条件无关 冒泡排序中产生的有序子序列一定是全局有序的

最好： 表正序 比较n-1 移动0次 O(1) n-1 n-1 表逆序 比较 i=1(n-i) 移动 i=13(n-i) O(n2) 时间 最坏：

平均:O(n2) 快速 排序 (*)

空间： 最坏情况下发生在两个区域分别包括 n-1 个元素 不稳定 和 0 个元素这种最大程度上的不对称发生在每层递归 上

1) 2) 3) 4)

快排算法的性能主要取决与划分操作的好坏 枢轴量的选择：第一个元素；头、尾、中间三个元素的中间 值；随机选择 内部排序算法中平均性能最优 在快速排序中并不产生有序子序列，但每一趟都把一个元素 放在最终位置上

log2(n+1) O(log2n) 最坏：n-1 O(n) 平均: O(log2n) 最好：

时间 最好O(nlog2n) 最坏O(n2) 平均O(nlog2n)