读书笔记-算法-第二章
第二章 排序
- 初级排序算法
- 排序就是将数组的主键按照某种方式排序
- 排序成本模型：我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数
- java的compareTo方法必须实现一个全序关系：
- 自反性：对于所有的v，v=v
- 反对称性：对于所有的v<w都有w>v，且v=w时w=v
- 传递性：对于所有的v，w和x，如果v<=w且w<=x，则v<=x
- 选择排序
- 基本步骤
- 找到数组中最小的那个元素
- 将它和数组的第一个元素交换位置
- 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置，如此反复
- 分析效率
- 对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换
- 为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息
- 可以看到，对于长度为N的数组，交换次数固定为N次，是所有数组中，交换步数最少的
- 简单，但效率颇低
- 基本步骤
- 插入排序
- 基本步骤
- 从索引1开始，对比索引1的数字和索引0的数字，如果索引0数字比索引1数字大，则两个数字交换位置
- 索引移到2，对比索引2和索引1所在数字，同样的，如果索引1比索引2数字大，则交换位置
- 接下来对比索引1和索引0，以此类推
- 分析效率
- 对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要(N^2)/4次比较以及(N^2)/4次交换。最坏情况下需要(N^2)/2次比较和(N^2)/2次交换，最好情况下需要N-1次比较和0次交换。
- 插入排序对于实际应用中常见的某些类型的非随机数组很有效
- 数组中每个元素距离它的最终位置都不远
- 一个有序的大数组接一个小数组
- 数组中只有几个元素的位置不正确
- 当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快
- 基本步骤
- 排序算法可视化
- 选择排序和插入排序效率对比
- 对于随机排序数组，两者的运行时间都是平方级别的
- 从大量数据实验来看，两者的运行时间没有数量级的差别，但是实际跑下来，插入排序会比选择排序快将近2倍
- 希尔排序
- 基本思路
- 使数组中任意间隔为h的元素都是有序的
- 一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组
- 在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便
- 基本步骤
- 确定一个间隔值h，一开始可以很大，为了方便，可以根据数组长度来确定h
- 其中一种h的算法，N为数组长度：
- int h = 1;
while(h<N/3) h=3*h+1;
- int h = 1;
- 其中一种h的算法，N为数组长度：
- 随后的基本过程和插入排序类似，只不过改成以h为长度
- 从索引h开始，对比索引h的数字和索引0的数字，如果索引0数字比索引h数字大，则两个数字交换位置
- 索引移到h+1，对比索引h+1和索引1所在数字，同样的，如果索引1比索引h+1数字大，则交换位置
- 接下来对比索引h和索引0，以此类推
- 完成以此以h为长度的排序后，将h缩减，比如将h/3，在重新开始上述循环，直到h=1的循环结束后，排序完成
- 确定一个间隔值h，一开始可以很大，为了方便，可以根据数组长度来确定h
- 分析效率
- 基本上，无法确切的计算出希尔排序的准确效率，只能说在各种实验中都比插入排序更加高效
- 即使最坏的情况下，也不会达到平方级别，接近于O((N^3)/2)
- 某种情况下，可以认为是性价比极高的排序算法，因为比较简单快速，且不需要用到额外的存储空间
- 希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大
- 基本思路
- 归并排序
- 基本思路
- 将一个大的数组分成两半，分别排序
- 将两个小的有序数组合并之后，进行归并排序
- 注意，归并的前提是两半的数组都已经分别有序
- 原地归并的基本步骤
- 先将所有元素复制到aux[]中，然后再归并回a[]中
- 左半边用尽（取右半边的元素）
- 右半边用尽（取左半边的元素）
- 右半边的当前元素小于左半边的当前元素（取右半边的元素）
- 右半边的当前元素大于等于左半边的当前元素（取左半边的元素）
- 递归的归并
- 和原地归并思路差不多，不过将每个半边再继续分一半，按照递归的思路不断切分成最小的数组进行归并
- 和原地归并思路差不多，不过将每个半边再继续分一半，按照递归的思路不断切分成最小的数组进行归并
- 分析效率
- 将大数组递归成更小数组，这个过程最多需要lgN步
- 最小数组只包含两个元素，仅需要进行一次位置交换
- 合并成一个大数组后，交换次数最多也是N步
- 省略一部分数学推导，时间复杂度是和N*lgN成正比的
- 从时间效率来说毫无疑问是高效的，然而缺点是越大的数组需要的额外数组越多，空间复杂度越大
- 改进空间
- 对于分割出来的小数组，可以不必每次都用归并排序，适当使用插入排序解决小数组，可以使得效率更高
- 研究一个新问题时，最好的方法是先实现一个你能想到的最简单的程序，当它成为瓶颈的时候再继续改进它
- 自下而上的归并排序
- 与原地归并的思路相反，不将大数组分割成小数组，而是直接从小数组出发，先两两归并，再四四归并，如此类推
- 与原地归并的思路相反，不将大数组分割成小数组，而是直接从小数组出发，先两两归并，再四四归并，如此类推
- 基本思路
- 排序算法的复杂度
- 排序算法的极限效率是lg(N!)~N*lgN次
- 证明过程和二叉树相关，看不太明白，需要研究的看书P386
- 准确的上界为软件工程师保证性能提供了空间
- 准确的下界可以为我们节省很多时间，避免因不可能的性能改进而投入资源
- 尽管归并排序很有可能是最高效的排序，然而现实中也很可能不使用归并排序
- 归并排序的空间复杂度不是最优的
- 在实践中不一定会遇到最坏情况
- 除了比较，算法的其他操作（例如访问数组）也可能很重要
- 不进行比较也能将某些数据排序
- 在随机生成的数组中，也证实了归并排序和希尔排序的效率差不多，只会快常数级别的效率
- 排序算法的极限效率是lg(N!)~N*lgN次
- 快速排序
- 基本思路
- 和归并排序类似的是，将一个大数组分成两个小数组，将两部分独立的排序
- 前提是数组需要打乱，并取出一个中间元素
- 此时将左右半边进行排序，左半边要求不大于中间元素，右半边要求不小于中间元素
- 完成后再将左半边和右半边进行递归处理，按照1-3的步骤
- 基本步骤
- 快速排序递归地将子数组a[lo..hi]排序
- 先用partition()方法将a[j]放到一个合适位置
- 然后再用递归调用将其他位置的元素排序
- 切分数组
- 如下所示，取出第一个数作为切分元素
- 分别维护数组两头的指针，向中间移动
- 左边找到比切分元素大的数字，右边找到比切分元素小的数字
- 交换两个数字的位置
- 不断重复这个过程，直到没有数字可以交换
- 注意事项：快速排序效率高，但是比较脆弱，稍不注意的点可能导致效率骤降
- 原地切分
- 不要在递归的切分方法中创建数组，而是传递初始数组对象进去处理
- 别越界
- 保持随机性
- 数组元素必须是乱序的，如有必要，可以在切分数组时，随机选择一个切分元素
- 终止循环
- 一个最常见的错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素
- 原地切分
- 分析效率
- 切分方法的内循环会用一个递增的索引将数组元素和一个定值比较
- 非常短小精悍的内循环
- 只要数组是随机的，那么平均而言，切分元素都能落在数组的中间，这样也就能保证快速排序的最好效率
- 将长度为N的无重复数组排序，快速排序平均需要2N*lnN次比较
- 最糟的情况就是每次选择切分元素都选到了最小的，这样需要(N^2)/2次的比较
- 总的来说，可以肯定的是对于大小为N的数组，快速的运行时间在1.39N*lgN的某个常数因子的范围之内。归并排序也能做到这一点，但是快速排序一般会更快（尽管它的比较次数多39%），因为它移动数据的次数更少
- 切分方法的内循环会用一个递增的索引将数组元素和一个定值比较
- 快速排序的改进
- 切换到插入排序
- 插入排序对于小数组的处理总是更加高效
- 设定数组切分到一定大小的时候，切换为插入排序
- 三取样切分
- 为防止切分元素的位置过于极端导致的效率下降，采用从小数组中取三个数中的中位数来作为切分元素
- 熵最优的排序（三向切分）
- 考虑和切分元素相等的情况
- 对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高得多
- 在实际应用中，不能忽视重复元素的影响
- 切换到插入排序
- 基本思路
- 优先队列
- 不是所有情况下都要数组完全有序，很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素
- 基于其目的需要实现两种功能：删除最大元素和插入元素
- 初级实现
- 无序数组
- 添加一段类似于选择排序的内循环的代码，将最大元素和边界元素交换然
- 有序数组
- 最大的元素总会在数组的一边，优先队列的删除最大元素操作就和栈的pop()操作一样了
- 链表表示法
- 无序数组
- 二叉堆
- 每个元素都要保证大于等于另两个特定位置的元素
- 这些位置的元素又至少要大于等于数组中的另两个元素
- 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序
- 堆的算法
- 对于某个节点K，父结点的位置为k/2，而它的两个子结点的位置则分别为2K和2K+1
- 用长度N+1的数组pq[]表示一个大小为N的堆，堆元素放在pq[1]至pq[N]中，不从0开始
- 当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。
- 如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆
- 插入元素：我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
- 删除最大元素：我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置
- 简而言之，插入元素是插到堆的末尾，然后再上浮到合适位置。删除元素，从顶端将最大元素和末尾元素交换位置，然后删除最大元素，再将末尾元素下沉到合适位置。
- sink方法的逻辑
- 输入k之后，将2k和2k+1的值进行比较（这两个值是k的子结点），找到这两个值中更大的那个
- 将k和1步骤中找到的更大值进行比较，如果k更小，则k和该值的位置交换
- 继续将k和子结点进行比较，重复该过程，直到k不比任何子结点小，或者到达最末尾后结束循环
- swim方法的逻辑
- 输入k之后，将k和k/2的值进行比较（k/2是k的父节点）
- 如果k比k/2更大，则将两个值的位置交换
- 继续将k和其父节点比较，重复该过程，直到k不比任何父节点大，或者到达根结点后结束循环
- 堆的效率
- 对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN+1）次比较，删除最大元素的操作需要不超过2lgN次比较
- 多叉堆
- 基于二叉堆的原理可以构建三叉堆
- 对于数组中1至N的N个元素，位置的结点大于等于位于3K-1、3K和3K+1的结点，小于等于位于(k+1)/3的结点
- 基于二叉堆的原理可以构建三叉堆
- 索引优先队列
- 给每个元素一个索引，从而使得优先队列中的元素可以被外部引用
- 理解这种数据结构的一个较好方法是将它看成一个能够快速访问其中最小元素的数组
- 在一个大小为的索引优先队列中，插入元素（insert）、改变优先级（change）、删除（delete）和删除最小元素（removetheminimum）操作所需的比较次数和lgN成正比
- 堆排序
- 由堆的上浮下沉过程可以对一个数组进行排序
- 用swim()保证扫描指针左侧的所有元素已经是一棵堆有序的完全树即可
- 基本思路
- 我们将原始数组重新组织安排进一个堆中
- 然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果
- 基本步骤
- 输入数组a[]后，先将其构造成堆
- 构造堆的方法是将索引小于N/2的元素都进行下沉操作，这样可以保证创造一个深度不超过lgN的堆，同时会把最大值放在头部
- 然后遍历堆，第一步将头部元素和末尾元素调换位置，再将末尾元素下沉到合适位置
- 第二次循环，将头部元素和倒数第二个元素调换位置，再将倒数第二个元素下沉到合适位置，以此类推
- 效率分析
- 是我们所知的唯一能够同时最优地利用空间和时间的方法
- 在最坏的情况下它也能保证使用～2NlgN次比较和恒定的额外空间
- 但现代系统的许多应用很少使用它，因为它无法利用缓存(?)
- 排序的应用
- 在一个有序的数组中查找一个元素要比在一个无序的数组中查找简单得多
- 应用领域：数据压缩、计算机图形学、计算生物学、供应链管理、组合优化、社会选择和投票等
- 使用comparator进行排序
- 如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的
- 排序算法比较
- 快速排序是最快的通用排序算法
- 内循环的指令很少
- 能够利用缓存
- Kendall tau距离就是在两组数列中顺序不同的数对的数目
- 例如，0316254和1036425之间的Kendalltau距离是4，因为01、31、24、54这4对数字在两组排列中的相对顺序不同，但其他数字的相对顺序都是相同的
- 使用快速排序中的切分法来查找中位数
- 按照快速排序的规则，选择第一个数作为切分元素，切分完成后，左边的数都小于它，右边的数都大于它
- 此时检查切分元素所在的位置，如果正好是数组元素的中间位置，则这个切分元素就是中位数，如果位置大于中间位置，则重新切分左半边，如果位置小于中间位置，则重新切分右半边
- 以此循环，直到切分元素的位置刚好在中间位置，就找到了中位数
