排序算法：插入排序，快排，归并排序【数据结构和算法入门3】

[@turingplanet4052]

欢迎正在找实习、全职、或跳槽的朋友，加入我们的刷题小组：bit.ly/3xKuOtv

[@minghuazhong3330]

Should we use smallerindex>=biggerindex?

[@yantao3217]

这是我看过讲时间复杂度和空间复杂度讲的最好的中文视频教程，没有之一。

[@micheallu7700]

mergesort 里那个第一个while 循环里应该是(leftstart

[@turingplanet4052]

Good catch！谢谢指正

[@MakeChinaGreatAgain-Ping]

归并排序两个方法都叫mergeSort么？重名了呀

[@amy00661]

插入排序(Insertion Sort)的時間複雜度公式應該是「n(n+0)/2 ≈ n^2」吧!? 因為每個元最多需要比較(n-1)次，比較總次數就是0 + 1 + … + n = n(n+0)/2 ≈ n^2

[@guyfancy8738]

大O阶计算时间复杂度本身就是估算时间复杂度，所以忽略点对最后结果影响小的部分，只关注最高次幂项，以此来估算时间复杂度的，所以你那个约等于没必要了

[@yiyang222]

请问为什么quicksort的空间复杂度是o(n)呢？code里都是在原来的array上操作并且没有引入新的space吧

[@hw1451]

要递归？

[@calasmurphy9578]

快排基于递归栈调用，空间复杂度和栈深度相同。快排每一次递归调用都会划分左右两个子表，执行快排的过程其实就是构造一棵二叉树，n个节点的二叉树最大高度是n,和递归调用的层数一致，复杂度都是o(n)

[@fredpaul9352]

视频中快排伪代码的partition方法中的第8行，rightindex-- 其实是biggerelementindex--; 是吧？！ 0v0

[@turingplanet4052]

嗯嗯~ 多谢指正

[@Dkevin09]

12:42

[@JINNINGXIAN]

可以问一下，mergesort在分的时候，时间复杂度是n还是log n

[@turingplanet4052]

logN。假设分层的次数为k，n被二分多少次到1呢？我们只需要计算 2^k = n，得出 k = logN

[@serana_english_progress]

有个关于qucksort的问题：根据代码，如果选最右边的pivot就是本组数列最大值，那第一次sort相当于没sort, 然后继续选最右边为pivot，死循环呀，没有办法sort。所以是不是每次quicksort要规定除了随后一次sort，选的pivot不能是每个partition里的最大值？希望能解答！谢谢！

[@chenzhang3851]

我的理解是最右边的pivot不是本列数组最大值， 而是选取它为“中轴值”（是多大多小都无所谓），最终目的是要把比pivot小的往左放，比pivot大的往右放

[@serana_english_progress]

@@chenzhang3851 对，但就是万一巧了， 最右边的值刚好就是本组数列最大值呢？所以那选最右边的值为pivot这个设定是不是有缺陷？

[@shiyangnie6738]

不会呀。即使右边是最大值，第一次sort以后，你把它放在最后面。然后下面两行代码，会缩小递归长度。 quickSort(array, left, partitionIndex - 1); quickSort(array, partitionIndex + 1, right); 举个例子。array [4,2,6] 第一次把6给排好，但是第二次变成了[4,2,6] left = 0， right = 1 与 [4,2,6] left = 3， right = 2，直到区间长度小于或者等于1(base case)，开始计算返回先前的递归值。

[@YS-ui8si]

Insertindex是向前指数的话 不需要写 insertindex = array.length -1吗？

[@turingplanet4052]

请问具体是哪个部分的疑问呢？

[@shiyangnie6738]

它的insertIndex是从第二个元素开始往后面一个一个插入排序，你说的这个insertIndex = array.length -1 是对最后一个元素插入排序。你得先把前面的排好序才能排后面的。一个挨着一个排。就像给身高排队，你得先从第二个人开始，不能直接就从最后一个人开始排，除非你是从后往前排。而这里是从前往后排。

[@jianghuafan8419]

@@shiyangnie6738 代码里写的是insertIndex = i -1，指的就是你说的从第i个开始往进插入，不知道我回答的是你说的问题吗？

[@mmmccc9028]

学了基础java 还是看不懂....

[@shiyangnie6738]

你哪里不懂呢？

[@sheltonsong6120]

讲得一点也不清楚

[@danqingreader8763]

这个快速排序讲的很清楚 你自己太菜回去再学一段时间