demo

演示1.3代码实现2自顶向下的归并排序2.1比较次数与访问次数的证明2.2代码优化2.3优化后代码实现3自底向上的归并排序3.1代码实现4排序算法的复杂度5稳定性5.1插入排序稳定5.2选择排序不稳定5.3希尔排序不稳定5.4归并排序稳定

归并排序除此之外还有

比较器Compartor不过本文暂且略过这一内容感兴趣的朋友建议移步视频自行学习总结。

参考目录

请自行搜索。

主要以该视频课顺序来进行笔记整理课程讲述的教授本人是该书原版作者之一

Robert

如果其中一个子数组已经没有元素则另一个子数组的元素直接放回原数组

1.3代码实现

edu.princeton.cs.algs4.Merge#merge

edu.princeton.cs.algs4.Merge#sort

上面分步实现的归并排序是属于自顶向下的归并排序。

官网给出了归并的分步结果图

截图自官网

比较次数和访问次数是衡量一个算法优劣与否的重要参考标准因此这里给出了相关的证明。

截图自视频

2N次用来复制2N次用来将排好序的元素移动回去另外最多比较2N次

视频中教授使用长度

一共有三种证明方式但说实话我看了几遍还是没太懂怎么算的哭先把证明方式贴出来

方式一图形法证明

命题F。

对于长度为N的任意数组自顶向下的归并排序需要½NlgN至NlgN次比较。

书中关于命题

归并排序虽然速度比较快但是也有一些缺点因此也提出了一些优化方案这里列出对应的章节

2.2.2.1

edu.princeton.cs.algs4.MergeX#sort

自顶向下的归并排序使用了递归的方式为了减少递归的操作又提出了自底向上的归并排序。

截图自官网

edu.princeton.cs.algs4.MergeBU#sort

这里使用了决策树来进行说明不过我觉得这一部分书本的说明不是很好有些地方说得云里雾里的……

还有对于命题

命题I。

没有任何基于比较的算法能够保证使用少于lgN!NlgN次比较将长度为N的数组排序。

Any

这一部分回顾了目前所讲到的四种算法插入排序、选择排序、希尔排序以及归并排序。

5.1插入排序稳定

通常而言看一个排序是否稳定一般是看它是否有长距离的交换可能使得一条记录越过某一条相同值的记录。

5.2选择排序不稳定

只要归并操作是稳定的那么归并排序算法就是稳定的操作是否稳定取决于代码怎么写。