0%

算法—排序

  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

选择排序

  • 步骤

    • 寻找数组内最小的元素
    • 与未排列的第一个元素交换位置.
    • 重复1 2 知道数组排列完成.
  • 代码

    • 内循环 比较当前元素与已知最小元素
    • 外循环 交换元素位置
  • 性质

    • 运行时间与输入无关..数组有序无序不影响时间.
    • 数据移动最少.交换次数 与 数组长度 为线性关系.
    • 长度为N的数组 , 选择排序 N2/2 次比较,及N次交换.
  • 分析

    • 最直观的排序算法.
    • 无法利用数组的初始状态进行优化.(后续重点)

冒泡排序

  • 步骤

    • 遍历未排列数组,比较两个相邻元素,依照规则 交换/不交换位置.
    • 重复1,直到完成数组排序.
  • 代码

    • 内循环 冒泡整个未排序数组
    • 外循环 控制内循环 冒泡范围
  • 分析

    • 可能是效率最差的
    • 实际效率与选择排序差不多.

插入排序

  • 步骤

    • 从第一个元素开始,该元素可以认为已经被排序
    • 取出下一个元素,比较已排序序列,找到新元素位置
    • 将新元素插入到该位置后
    • 重复步骤直到排序完成.
  • 代码

    • 取出新元素
    • 内循环查找新元素位置
    • 插入新元素
    • 外循环控制
  • 性质

    • 随机数组N, 平均需要 ~ N2/4 次比较及 ~N2/4 次交换.
    • 最坏 N2/2 次比较 N2/2 次交换
    • 最好 N-1 次比较 0 次交换(已经排序好的….😂)
  • 分析

    • 考虑了数组的初始状态,对于大多数元素有序的数组,插入排序可能是最快的.
    • 但对于随机数组 还不够.
  • 优化

    • 查找新元素位置: 二分法查找.而不是遍历.
    • 插入新元素时,算法第四版 建议,内循环改为类似冒泡方式,将大元素右移

希尔排序

  • 对插入排序分析时,有这样的结论: 对于大多数元素有序的数组,插入排序时间最快,时间为线性级别.
    将任意输入的数组 大多数元素有序,然后最后使用 插入排序.

  • 插入排序对于 随机数组的瓶颈 在于,一个元素到达正确位置,一次只能移动一位.那么一次可以移动多位,交换至很远位置,可以改善插入排序的性能.

  • 思路: 将数组等间隔 h 分裂,进行插入排序.拆分后的子数组,插入排序成本较低,进行插入排序.

  • 完成后,原数组的有序性增加 插入排序成本降低,之后再进行颗粒度更细的拆分-排序.一级一级的降低 插入排序成本.直到最后进行 h=1的插入排序.

  • 步骤

    • 对数组进行间隔 h 的插入排序.
    • 依照递增序列,取 h 值,直到 h = 1,为止,排序完成.
  • 代码

    • 内循环为 间隔 h 的插入排序
    • 外循环为 计算 h 值的递增序列.
  • 性质

    • 希尔排序的性质并不容易概括,实际上没有完整概括.
    • 目前可以证明的:希尔排序的运行时间 达不到 N2 级别.
  • 分析

    • 考虑了数组初始状态.是如今提到的排序算法中,第一个可以适用与大容量数组排序的.
    • h 递增序列的选择,会很大程度上影响希尔排序效果.实际工程中适用那种,需要自行选择.
    • 嵌入式系统中没有快排等库函数可选时,首选希尔排序.之后再考虑其他排序算法.

归并排序

  • 归并排序的实现与插入/希尔/选择排序不同.

  • 归并排序依赖于 归并操作.

    • 归并 : 将两个有序数组 合并 为1个有序数组.
  • 自顶向下 递归

    • 实际上是一个 sort 的递归调用.
    • 将数组分为 两个子数组
    • 对子数组调用 调用sort
    • 再对第二层子数组 调用 sort
    • 直到最终子数组元素个数为1.递归返回 开始执行 merge()操作.
  • 自底而上 迭代

    • 直接归并 子元素为1 的各个数组到 子元素为2的数组.
    • 再归并子元素为2 的各个数组 到子元素为4的数组.
    • 最后 可能存在 数组元素不相等,但是不影响归并.
    • 直到归并的数组元素为 N.
  • 实际上 两者执行的过程是一样的,只是调用的角度不同.

  • 性质

    • 空间复杂度不是最优.
    • 时间复杂度 NlogN
    • 空间复杂度 N
  • 优化

    • 原理相同,对小的子数组 使用其他高效排序,再归并.

快速排序

  • 应用最为广泛. 原地排序 时间成本 NlogN

  • 但是! 坑不少…

  • 原理

    • 对于数组中 某个元素 都进行切分操作,大于/小于 该元素的所有元素 都在 一边. 将数组切分为2个子数组. 递归,直到切分子数组元素个数为1,完成排序.
    • 与归并排序 在数组分解上 一致.
  • 步骤

    • 取出数组中某个元素 作为切分元素.
    • 对数组执行切分.
    • 对子数组执行 1 2 直到子数组元素个数为1.递归.
    • 原地切分,创建大量新对象性能上不可接受
    • 保证访问不越界.
    • 慎重处理最大最小元素.
    • 相同元素谨慎处理.
  • 性能改进

    • 切分元素对性能影响及其重要.
      • 最糟糕情况: 大部分元素有序,使用极值去切分.
      • 为避免这种情况,快排之前,将输入数组乱序处理.
      • 对于大型数组 取切分元素时 考虑去3 选 1.
    • 小数组
      • 使用切换到插入排序.
    • 重复元素
      • 一分为二,对于存在大量重复元素的数组,无效的比较次数较多.
      • 改为 三取样切分

三切分取样

  • 切分时,不再一分为二,改为 < = >.三部分
  • 三项切分的信息量最优.
  • 对于存在大量重复元素的数组,三切分取样,直接将时间 由 NlogN 降低到了 N .