5.4归并排序与快速排序算法及分析（Python进阶-数据结构与算法）课件

归并排序与快速排序算法及分析 数据结构与算法（Python版） ❖ 下面我们来看看分治策略在排序中的应用 ❖ 归并排序是递归算法 ， 思路是将数据表持 续分裂为两半 ， 对两半分别进行归并排序 递归的基本结束条件是：数据表仅有1个数据项 ,自然是排好序的； 缩小规模：将数据表分裂为相等的两半，规模减 为原来的二分之一； 调用自身：将两半分别调用自身排序，然后将分 别排好序的两半进行归并，得到排好序的数据表 数据结构与算法（Python版） 归并排序Merge Sort 0 归并排序Merge Sort 0 数据结构与算法（Python版） 归并排序：代码 0 数据结构与算法（Python版） 拉链式交错把左右半部 从小到大归并到结果列表中 基本结束条件 递归调用 归并左半部剩余项 归并右半部剩余项 另一个归并排序代码（更Pythonic） 数据结构与算法（Python版） 0 ❖ 将归并排序分为两个过程来分析： 分裂和 归并 ❖ 分裂的过程 ， 借鉴二分查找中的分析结果 , 是对数复杂度 ， 时间复杂度为O(log n) ❖ 归并的过程 ， 相对于分裂的每个部分 ， 其 所有数据项都会被比较和放置一次 ， 所以 是线性复杂度 ， 其时间复杂度是O(n) 综合考虑，每次分裂的部分都进行一次O(n)的数 据项归并，总的时间复杂度是O(nlog n) 数据结构与算法（Python版） 归并排序：算法分析 0 ❖ 最后 ，我们还是注意到两个切片操作 为了时间复杂度分析精确起见， 可以通过取消切片操作，改为传递两个分裂部分 的起始点和终止点，也是没问题的， 只是算法可读性稍微牺牲一点点。 ❖ 我们注意到归并排序算法使用了额外1倍 的存储空间用于归并 ❖ 这个特性在对特大数据集进行排序的时候 要考虑进去 数据结构与算法（Python版） 归并排序：算法分析 0 ❖ 快速排序的思路是依据一个“ 中值 ”数据 项来把数据表分为两半： 小于中值的一半 和大于中值的一半 ， 然后每部分分别进行 快速排序（递归） 如果希望这两半拥有相等数量的数据项，则应该 找到数据表的“ 中位数 ” 但找中位数需要计算开销！要想没有开销，只能 随意找一个数来充当“ 中值 ” 比如，第1个数。 数据结构与算法（Python版） 快速排序Quick Sort 0 ❖ 快速排序的递归算法“递归三要素”如下 ❖ 基本结束条件：数据表仅有1个数据项， 自然是排好序的 ❖ 缩小规模： 根据“ 中值 ” ， 将数据表分为 两半 ， 最好情况是相等规模的两半 ❖ 调用自身： 将两半分别调用自身进行排序 （排序基本操作在分裂过程中） 数据结构与算法（Python版） 快速排序Quick Sort 0 ❖ 分裂数据表的目标：找到“中值”的位置 ❖ 分裂数据表的手段 设置左右标（left/rightmark） 左标向右移动，右标向左移动 • 左标一直向右移动，碰到比中值大的就停止 • 右标一直向左移动，碰到比中值小的就停止 • 然后把左右标所指的数据项交换 继续移动，直到左标移到右标的右侧，停止移动 这时右标所指位置就是“ 中值 ”应处的位置 将中值和这个位置交换 分裂完成，左半部比中值小，右半部比中值大 数据结构与算法（Python版） 快速排序：图示 0 快速排序：图示 0 数据结构与算法（Python版） 数据结构与算法（Python版） 基本结束条件 快速排序：代码 递归调用 0 分裂 北京大学地球与空间科学学院中/陈 /点201，9 也是分裂点 快速排序：代码 向左移动右标 数据结构与算法（Python版） 左右标的值交换 向右移动左标 左右标初值 中值就位 两标相错就结束移动 选定“中值” ❖ 快速排序过程分为两部分： 分裂和移动 如果分裂总能把数据表分为相等的两部分，那么 就是O(log n)的复杂度； 而移动需要将每项都与中值进行比对，还是O(n) ❖ 综合起来就是O(nlog n)； ❖ 而且 ， 算法运行过程中不需要额外的存储 空间。 数据结构与算法（Python版） 快速排序：算法分析 0 ❖ 但是 ， 如果不那么幸运的话 ， 中值所在的 分裂点过于偏离中部 ， 造成左右两部分数 量不平衡 ❖ 极端情况 ， 有一部分始终没有数据 ， 这样 时间复杂度就退化到O(n2) 还要加上递归调用的开销（比冒泡排序还糟糕） 数据结构与算法（Python版） 快速排序：算法分析 0 ❖ 可以适当改进下中值的选取方法 ， 让中值 更具有代表性 比如“三点取样 ”，从数据表的头、尾、中间选 出中值 会产生额外计算开销，仍然不能排除极端情况 ❖ 还有什么采样具有代表性？ 数据结构与算法（Python版） 快速排序：算法分析 0 $$