校招算法梳理(二)

校招算法梳理第二篇
荷兰国旗问题
快排及其改进
堆与堆排
排序的稳定性

1.荷兰国旗问题

荷兰国旗问题:小于放左边,大于放右边,等于放中间,主要是partition的过程
要求空间复杂度O(1),时间复杂度O(n)
引出快排的思想,可用荷兰国旗问题给快排做加速

画小于/大于区域,把数组里面的数往这两个区域发货。小于区域推着等于区域往右走,中间的都是待定区。
有less,more,current三个指针,遍历过程中current逼近more为终止条件。

  • current遇到等于num的,直接跳下一个current++。
  • current小于num的,将小于区域的下一个位置less++的数交换,小于区域扩一下。
  • current当前指的数大于num的,将current位置与大于区域前一位置more–的数交换,大于位置more扩一下。继续判断current位置的数和num的大小。
    这三块只要有一块区域不存在的话,此算法也不会出问题。

    2.快排及其改进

    经典快排:一个数组每次取最右边的数num,小于num的放左边,大于num的数放右边,num放中间。然后num左边的部分去递归,num右边的区域也去递归。每次确定num的位置,但小于区域和大于区域也可能有num,需要进行多余的排序。

    改进的快排:等于的num都放中间,位置确定不变,再拿小于区域和大于区域的去做递归。每次能确定多个等于区域的数的位置。返回等于区域的num的左右边界,多个num。大于区域最后的num一开始都不参与遍历,后面再归位。可以节省一个变量。

经典快排的问题,小于区域和等于区域很可能不是等规模的,和原始数据状况有关。

  • 引入随即快排,每次随机选一个数,和最后位置的数交换,用随机选的数去划分。随即快排的复杂度是一个长期期望的复杂度。O(nlogn),最常用的排序,速度很快。代码简洁,意味着常数项很少,工程上大量使用。额外空间复杂度是O(logn),每次需要记住等于区域,每次存了划分区域的index空间,数组能被二分多少次。使用额外空间的长期期望是O(logn)。工程上不允许递归函数出现,非递归的版本,准备一个递归函数代价较高,会将所有与业务有或没有的变量存起来,常数时间消耗较大,也会不安全。
  • 哈希处理,来规避数据状况的问题。

MergeSort有许多数组的copy过程,常数项太多,额外空间复杂度为O(n)。
排序的稳定性不在于时间复杂度有时快,有时慢。

3、堆排

重要的是堆结构,即完全二叉树,叶子结点从左往右补。堆可以用数组来实现的。父节点(i-1)/2
大根堆——任何一颗子树的头部是其最大值。

几乎所有的贪心问题都是用堆结构来解决的,重中之重。

数组建立大根堆

0到n-1想象成一颗完全二叉树,0-i也是完全二叉树,数据一个个的加到数里面,判断其与父节点的大小,大则往上换。在0位置的时候,arr[0] = arr[(i-1)/2],任何一个数加进来完全二叉树,只和完全二叉树形成的高度比较,调整代价为O(logN),这是一个非常大的进步。

复杂度分析

第一个数加到大根堆里面,是O(1)操作,建立一个大根堆的复杂度为log1+log2+log3+…log(n-1)=O(N)。

heapinsert操作,新增节点加入大根堆里面比父节点,同时往上调整的过程O(log N)。

heapify假设数组中有一个值发生变化,如何重新调整为大根堆。找到他左右两个孩子,最大的数和父节点交换,继续下沉比较的过程。

用heapsize标记已形成堆是否越界,index 、left、left+1

堆操作举例:用堆结构取中位数

数进入数组,开始建大根堆,再建一个小根堆。需要一个减堆操作,即开始的第一个数进大根堆,第二个数时若比第一个数小,则进大根堆,否则进小堆。若进大堆,则将大堆根节点弹出,heapsize-1,大堆最后一个数换到根节点上,进行一个heapify操作,再变成大根堆,弹出的数加入小堆。

headsize差值大于1,则弹出来一个进入另外一个堆。大堆的弹出最大值进小根堆,小根堆弹最小值进大根堆,一定是较小的N/2放在大根堆,较大的N/2进小根堆。

堆排序

时间复杂度O(NlogN),空间复杂度O(1)

利用堆结构来排序

  • 数组变成大根堆(未必有序)
  • 堆节点与堆最后一个位置数换位,进行下沉操作,最大的数就变到了数组末尾,堆heapsize-1,接着调整。

4、排序的稳定性

排序的稳定性指,排序后,能否保证相同的数在原始数列中相对次序不变。

现实世界的业务往往需要稳定性,比如按age排序,其他字段比如身高,是上次排序留下来的信息,可能会导致混乱,需要排序后保留原始信息。

  • 冒泡排序的稳定版,实现思路,大值往下沉,遇到相同的数不交换,利用下一个位置的数继续冒泡。
  • 插入排序的稳定版,将最后拿来交换的数与前面的数比较并插入,若相等,则不交换。
  • 选择排序,选全局最小数和0号元素交换,无论如何实现都做不到稳定。

(插图,前面连续很多相等的数,全局最小的数在后面,那么和第一个位置的数交换后,这些相同次序的数顺序就变化了)

  • 归并排序稳定版,merge的时候,若左边右边区域的数相等,优先拷贝左区域的,保证右区域的相等的数不跨到左区域即可。
  • 快排做不到稳定,数组中随机选数,小于放左边,等于放中间,大于放右边。(论文级别难度的是可以做到的稳定)partion过程中做不到稳定性,数组中随机选一个数,后续展开
  • 堆排做不到稳定,因为它在交换过程中不会关注相等值的。插图,heapInsert 大数上浮的过程中,就已经破坏次序。 

工程上的综合排序算法

数组中是基础类型(5种)——快排

自定义的class(很多字段,年龄分数等)——归并

数组长度很短(小于60)——插排(虽然它时间复杂度很高,但常数项很低,小样本情况下飞快)

工程上写归并、快排的时候,以递归的方式将其划为子问题,base case是L=R,现在改为L-60,终止条件设置为里面再来一个插排。

有关排序问题的补充

归并排序额外空间复杂度可以做到O(1),但是非常难,可以搜索“归并排序内部缓存法”

快排可以做到稳定性,可以搜“01 stable sort”

partition过程、奇数偶数,额外空间复杂度O(1),都做不到稳定性。

题目举例

整数数组中,奇数放左边,偶数放右边,奇数、偶数之间分别维持原来的相对次序。能否做到空间复杂度O(1),时间复杂度O(n)。=>快排的稳定性(01标准)

-------------    本文结束  感谢您的阅读    -------------
胡想成 wechat
欢迎关注个人公众号!
您的支持,是我装逼的最大动力!

本文标题:校招算法梳理(二)

文章作者:胡想成

发布时间:2019年08月21日 - 16:08

最后更新:2020年03月14日 - 10:03

原始链接:xchu.net/2019/08/21/算法2/

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0许可协议,转载请注明出处!