hunterhug

> 菜鸡提问：关于提前结束循环的控制变量didSwap的位置及功能的问题： 1.原代码中didSwap的位置代表的功能：查看第一轮交换是否发生交换行为，如果发生就继续进行冒泡排序，如果没有发生，说明原序列是排序好的，就结束循环。 2.改变didSwap的位置，可以检查每一轮交换中是否发生交换行为，一旦没有，则说明已经排序好了，就立即结束循环。 > > 代码如下： > > ``` > package main > > import "fmt" > > func BubbleSort(list []int) { > n := len(list) > // 在一轮中有没有交换过...

> @baici1 > 你在自底而上归并排序里面对于空间复杂度的分析有问题！ > 从你的描述中感觉空间复杂度只和函数递归栈有关，但是你的算法中用到一个N长度的辅助数组，其实我觉得空间复杂度为O(N)。 > 这是我的看法。 文章下面的手摇算法就节省了辅助数组的空间。如果没有原地排序，你确实可以说空间复杂度是O(N)，但是根据上下文，我们讨论的是两种方法的区别，空间上的复杂度只要考虑的是递归，自顶向下空间复杂度更大。

> @baici1 > 那个手摇算法在leetcode上面使用，我觉得可以填上去。 > [题目：剑指Offer58-II.左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/) > leetcode 还是有用的！哈哈哈哈哈哈 实际上，不是leetcode有用，你要明白这一点。

快速排序用得比较多，有必要学习

> 问一个问题： 快排的计算公式`T(n) = 2*T(n/2) + O(n)` > > 下面的具体计算的时候是 `T(n) = 2*T(n/2) + n/2` > > 为什么是 `O(n)=n/2`? 你可以接着往下看，最好情况和最差情况。分析最好情况时认为 `O(n)=n/2`。

> > 你可以接着往下看，最好情况和最差情况。分析最好情况时认为 `O(n)=n/2`。 > > 在这里我想跟你 battle 一波。 我觉得你的 n/2 是有问题的。 举例：在这一组数组中`[4,1,3,2,6,5,7]`，对于第一次的遍历 4 就会放在中间，就是最好的情况！ 但是其实在`partition`,会比较 5 次。还差一次的比较就是后面`array[i] >= array[begin]` 说到底你还是比较了 6 次，也就是 n 次。 > > 快排的时间性能不是取决于单次的比较，而是递归的深度。 最好的情况是每次都平均分割，他的深度就是 `log2(n)`...

算法分析，是很重要的。

Docsify风格的 https://hunterhug.github.io/goa.c 。

图论算法很快会补充。。

内容如有纰漏或者笔误，可以在评论区指出，🎉