【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? )
• 消除递归(用栈，队列?)

参考资料

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