常用的内部排序

常用的内部排序 总结 排序的目的 为了快速查找 对于一个排序算法来说 一般从下面三个方面来衡量算法的优劣 1 时间复杂度 它主要是分析关键字的比较次数和记录的移动次数 2 空间复杂度 分析排序算法需要多少辅助内存 3 稳定性 若两个记录 A 和 B 的关键字相等 但排序后 A 和 B 的先后次序保持不变 则 称这种算法是稳定的 反之 就是不稳定的 内部排序的分类 选择排序 直接选择排序 堆排序 交换排序 冒泡排序 快速排序 插入排序 直接插入排序 折半插入排序 Shell 排序 归并排序 桶式排序 基数排序 直接选择排序 SelectSort 思路 经过 N 1 趟比较 每趟比较选出第 N 大 或者小 的元素放在第 N 个位置 时间效率 假设有 n 项数据 数据交换的次数最多为 n 1 次 但是程序比较大次数较多 总体来说 其时间效率为 O n2 空间效率 只要一个附加程序单元用来交换 其空间效率为 O 1 稳定性 不稳定 堆排序 HeapSort 堆的概念 1 完全二叉树 根节点索引为 0 2 大顶堆 大根堆 ki k2i 1 且 ki k2i 2 及父节点大于子节点 根节点最大 3 小顶堆 小根堆 ki k2i 1 且 ki k2i 2 及父节点小于子节点 根节点最小 堆排序的步骤 1 建堆 A 第一趟 0 n 1 建堆 找出最大或最小值 把最大或最小放在最后一个节点 B 第二趟 0 n 2 建堆 找出最大或最小值 把最大或最小放在最后一个节点 C 依此类推 2 堆的根节点和最后一个节点交换 因为根节点是堆中的最大值或最小值 堆排序需要经过 n 1 次建堆 每次建堆的左右就是选出最大值或最小值 因此堆排序的本 质上是一种选择排序 堆排序与直接选择排序的差别在于 堆排序可通过属性结构保存部分比较结果 可减少比 较次数 时间效率 需要 n 1 次建堆 每次建堆的本身的耗时为 log2n 则时间效率是 O nlog2n 空间效率 堆的空间效率很高 它只需要一个附加程序单元用来交换 其空间效率为 O 1 堆排序是不稳定的 冒泡排序 BubbleSort 思路 比较 n 1 趟 把相邻的两位进行比较 较大的元素放在后面 冒泡排序每趟结束交 换后 不仅能将当前最大值挤出最后面的位置 还能部分理顺前面其他元素 时间效率 最好的情况 初始已经有序 比较 n 1 次 无交换 最坏情况 倒序 比较 n n 1 2 移动 n n 1 3 2 空间效率 O 1 冒泡排序是稳定的 快速排序 QuickSort 思路 从待排的数据序列中任取一个数据 如第一个数据 作为分界值 所有比它小的数 据元素一律放在左边 所有比它大的数据一律放在右边 经过这样一趟下来 该序列形成 左右两个子序列 左边都比分界值小 右边序列中数据元素的值都比分界值小 1 定义一个 i 变量 i 变量从左边第一个索引开始 找大于分界值的元素的索引 并用 i 记录它 2 定义一个 j 变量 j 变量从右边第一个索引开始 找到小于分界值的元素索引 并用 j 来记录它 3 如果 i j 时间效率 每趟确定的元素呈指数增长 空间效率 需要使用递归 而递归要使用栈 空间效率 O log2n 不稳定算法 直接插入排序 思路 依次将待排序数据元素按期关键字大小插入前面的有序序列 时间效率 O n2 空间效率 O 1 稳定性 稳定 折半插入排序 思路 基本上和直接插入排序相同 但是利用了以排序序列的规律性 采用折半查找法找 到插入位置 时间效率 O n2 空间效率 O 1 稳定性 稳定 Shell 排序对直接排序进行了简单的改进 ta 它通过加大插入排序中元素的间隔 并在这些 有间隔的元素中进行插入排序 从而使数据项大跨度移动 当这些数据项排过一趟后 shell 排序算法减小数据项的间隔再来排序 依次进行下去 进行这些排序时代数据项直接 按的间隔被称为增量 习惯上用字母 h 来表示这个增量 常用的 h 序列是从 1 开始 通过如下公式产生 h 3 h 1 当 h 很大时 数据项每每一趟排序需要移动元素的个数很少 但数据项移动的距离很长 当 h 很小时 每一趟排序需要移动的元素个数增多 但是此时数据项已经接近它们排序后 的最终的位置 这对于插入排序可以更有效 时间效率 O 3 2n O 7 6n 空间开销 O 1 稳定 归并排序 思路 将两个 或以上 有序序列合并成一个新的有序序列 细化来说 先将