严蔚敏数据结构课本源码及习题解析排序.docx

排序类别基本思 想排序算法复杂度分析稳定性排序特点插入排序每次将一 个待排序 记录按其 关键字大 小插入到 前面已排 好的子序 列中直接插入排序空间：0(1)稳定适用于顺序与链式存储时间最好:表正序比较n-1次,不移动0(1)最坏:表逆序比较力修，移动2二介工)0(n2) L 平均：O(n，)折半插入排序空间：0(1)稳定仅仅减少了比较元素，比较次数与待排序表初始状态无关口寸间比较QHog丹与初始状态无关移动：0(2与初始状态有关平均：0(2希尔排序时间复杂度依赖于增量序列的函数0(nA1.3)不稳定，相等关键 字记录被 划分到不 同的子表确定增量：通过比较第一趟排序结果与初始条件，找第一个变续的关键字，再与该关键字原位置对比确定增量交换排序根据序列 中两个元 素关键字 的比较结 果来对换 这两个记 录在序列 中的位置冒泡排序空间0(1)稳定，相 邻比较相 等不换位1)用flag控制比较次数：若有flag,则比较次数与初始条件有关；若没有flag,则比较次数与初始条件无关2)冒泡排序中产生的有序子序列一定是全局有序的时间最好:表正序比较n-l移动。次0(1)最坏:表逆序比较天加力移动鸡如-i) 0(2平均:0(2快速排序(*)空间：最坏情况下发生在两个区域分别包括n-1个元素 和0个元素这种最大程度上的不对称发生在每层递归 上最好 Jlog2(n+loQog2n)最坏：nT 0(n)平均：。/刈不稳定1)快排算法的性能主要取决与划分操作的好坏2)枢轴量的选择：第一个元素；头、尾、中间三个元素的中间值；随机选择3)内部排序算法中平均性能最优时间 最好O(nlog4最坏O(lY)平均O(nlog44)在快速排序中并不产生有序子序列，但每-趟都把一个元素放在最终位置上选择排序每一趟在 选择一个 特定元素 放入特定 位置简单排序空间0(1)稳定最好比较吗11移动0。(2时间:最坏:比较里 移动3(n-1)0(2平均:。(2堆排序(*)空间0(1)不稳定逻辑上的树形结构(完全二叉树)，顺序存储从1开始展堆:也!1依次进行调整(整体向上，依次向下)乂、输出(而除)：堆底元素送入堆顶，向下调整 由入：新结点放在堆的末端，向下调整时间 0(n Iog2 n)归并排序将两个或 两个以上 的有序表 组合成一 个有序表2路归 并(*)空间0(n)稳定M- flogjNM：趟数K：路数 N：个数时间 0(n Iog2 n)基数排序多关键字 排序，借 助分配和 收集两种 操作空间0(r)稳定按基数个数构造辅助队列(r)，按关键字个数确定分配收集的操作次数时间 0(d*(n+r)d:d趟收集分配；n:n个元素；ur个队列