数据结构-各种排序算法的比较

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

排序 类别插入 排序

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

排序 算法直接 插入 排序 空间：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)

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

选择 排序

每一趟在 选择一个 特定元素 放入特定 位置

简单 排序

空间 O(1)

稳定n(n-1) 2

最好： 比较

移动0 O(n2)

n(n-1) 比较 2 移动3(n-1)O(n2) 时间 最坏：

平均:O(n2)堆排 空间 O(1) 不稳定 逻辑上的树形结构(完全二叉树) ,顺序存储从 1 开始i 2i 建堆：n 1 依次进行调整(整体向上，依次向下) 2 输出(删除):堆底元素送入堆顶，向下调整 2i+1 插入：新结点放在堆的末端，向下调整

序 (*) 时间 O(n log2 n)

归并 排序

将两个或 两个以上 的有序表 组合成一 个有序表

2 路归

空间 O(n)

稳定

并 (*) 时间 O(n log2 n)

M= logkNM:趟数 K:路数 N:个数

基数 排序

多关键字 排序，借 助分配和 收集两种 操作

空间 O(r) 时间 O(d*(n+r)) d:d 趟收集分配；n:n 个元素；r:r 个队列

稳定

按基数个数构造辅助队列(r) ,按关键字个数确定分配

收集的操 作次数