我还记得我第一次在接受采访时 遇到一个排序问题 采访者在桌子上滑出一个白板标记,并说 : “ 把这百万个整数集合起来 — — 告诉我为什么你选择了你的方法。 ” 我的大脑直接进入了我在CS101学过的 信任的旧泡沫。
我开始写嵌入式循环,感觉像Neo在慢动作中躲过子弹,只是为了意识到跑步时间正在向O(n2)爬去.
在痛苦的几分钟后,我可以看到采访者的眼睛闪闪发光 — — 并不是因为我错了,而是因为我正在用大锤来裂开坚果.
那一刻引发了一场探索: 是什么使得一个排序算法真正有效, 我怎么知道何时可以找到它?
以及深夜YouTube深潜。
答案不断指向一个感觉像发现隐藏的作弊代码的算法:并购.
启示录( 透视) 那么,为什么合并排序 工作这么好?
这不仅仅是分割和合并的问题,而是保证每一层次的重复都做线性的工作,无论输入是如何安排的。
将一个没有种类的阵列视为一堆乱七八糟的LEGO砖.
合并排序首先将堆积分为两半,然后再次减半,直到每个子小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小 魔法发生于合并步骤中:我们取出两个已经分型的子阵列,用两个指针走过它们,总是取出更小的前方元素并附在结果上.
因为每个小阵列都经过排序,我们从不需要回头看;我们只是一次提出一个指针.
该行走是合并的 O(n) : 每个元素在被放入输出阵列时都会被检查一次 。
由于我们拆分了阵列对数2n倍(每等能将大小减半),因此我们在每个对数对数2n等进行O(n)合并.
将它们相乘并获得 O(n logn n) 最坏的情况时间, O(n) 在合并时使用临时缓冲器的额外空间 。
最好的是这个保证能保证任何输入分布 — — 已经排序、反排序、随机或甚至重复。
合并排序是稳定的,意思是等元保持其原有的相对顺序,当您用多键排序复杂对象时,这个属性很重要.
连接电源( 代码和示例) 让我们看看算法在起作用。
下面是Python中一个干净,迭代的版本,它排序了一个整数列表.
我补充了一些评论, 常见陷阱(避免的“老板”) 忘记了基础案例 如果你不停止长度为1, 你最后会出现无限的复发和堆积溢出。
使用合并内部 – 该操作是 O(n) , 因为它转移了所有剩余元素, 将整个合并变为 O(n2) 。
总是使用显示的索引指针。
忽视稳定- 如果你在比对等键时用它替换, 你可能会无意中破坏这种键。
Real-World Interview problem 1 — 计算倒置 给定数组, 计出存在多少对( i, j) , 以至于 i < j and arr[i] > ar[j] 。
为什么合并排序?
合并步骤自然算倒数:每当我们从左前的右下方阵列中选择一个元素时,左下方阵列中的所有剩余元素都会与该元素相倒数.
通过合并时添加一个计数器,我们用 O(n log n) 时间用 O(n) 额外空格来解决问题.
问题2 – 在 O(n log n) 时间和 O(1) 额外空格中, 排序链接列表 排序单行链接列表 。
合并 排序在这里闪亮,因为它只需要顺序访问。
您可以使用快/ 慢指针技术将列表拆分, 递归排序每个半个, 然后通过重接节点合并 – 不需要额外的数组 。
这两个问题都经常出现在技术访谈中, 因为他们测试你是否理解了算法背后的原因, 而不仅仅是方法。
为什么这个新权力事务与合并排序结合, 您可以处理大型的数据卡