【8.4】交换排序

一、冒泡排序

算法思想: 不停地比较相邻的记录,如果不满足排序要求,就 交换相邻记录,直到所有的记录都已经排好序

检查每次冒泡过程中是否发生过交换,如果 有,则表明整个数组已经排好序了,排序结束

  • 避免不必要的比较

算法分析

  • 稳定
  • 空间代价:Θ(1)
  • 时间代价分析

  • 时间代价结论
    • 最大,平均时间代价均为Θ(n^2)
    • 最小时间代价为Θ(n):最佳情况下只运行第一轮循环

二、快速排序

  • 算法思想

    • 选择轴值 (pivot)
    • 将序列划分为两个子序列 L 和 R,使得 L 中所有记录 都小于或等于轴值,R 中记录都大于轴值
    • 对子序列 L 和 R 递归进行快速排序
  • 20世纪十大算法

    • Top 10 Algorithms of the Century
    • 7. 1962 London 的 Elliot Brothers Ltd 的 Tony Hoare 提出的快速排序
  • 基于分治法的排序:快速、归并

分治策略的基本思想

  • 分治策略的实例

    • BST 查找、插入、删除算法
    • 快速排序、归并排序
    • 二分检索
  • 主要思想

    • 划分
    • 求解子问题 (子问题不重叠)
    • 综合解

快速排序分治思想

轴值选择

  • 尽可能使 L, R 长度相等

  • 选择策略:

    • 选择最左边记录
    • 随机选择
    • 选择平均值

一次分割过程

  • 选择轴值并存储轴值
  • 最后一个元素放到轴值位置
  • 初始化下标 i, j,分别指向头尾
  • i 递增直到遇到比轴值大的元素,将此元素覆盖到 j 的 位置;j 递减直到遇到比轴值小的元素,将此元素覆盖 到 i 的位置
  • 重复上一步直到 i==j,将轴值放到 i 的位置,完毕

快速排序算法

分割函数

时间代价

  • 长度为n的序列,时间为 T(n)

    • T(0) = T(1) =1
  • 选择轴值时间为常数

  • 分割时间为 cn

    • 分割后长度分别为 i 和 n-i-1
    • 左右子序列 T(i) 和 T(n-i-1)
  • 求解递推方程

    • T(n) = T(i) + T(n - 1 - i) + cn

最差情况

最佳情况

等概率情况

也就是说,轴值将数组分成长度为 0 和 n-1, 1 和 n-2,… 的子序列的概率是相等的,都为 1/n

快速排序算法分析

  • 最差情况:

    • 时间代价:Θ(n2)
    • 空间代价:Θ(n)
  • 最佳情况:

    • 时间代价:Θ(nlog n)
    • 空间代价:Θ(log n)
  • 平均情况:

    • 时间代价:Θ(nlog n)
    • 空间代价:Θ(log n)

三、思考

  • 冒泡排序和直接选择排序哪个更优
  • 快速排序为什么不稳定
  • 快速排序可能的优化
    • 轴值选择 RQS
    • 小子串不递归 (阈值 28? )
    • 消除递归(用栈,队列?)

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学