很久之前研究过快排，是的，很久之前。
当时网上随便看的文档没有很详细，再加上本身悟性不太高，就没有搞懂。会写，但是不太理解，为什么多选几次基数比几次大小就排好序了？
最近在看之前没看完的《算法图解》，先看了分治，又紧接着看了快排。才算是把这个问题想明白。
快排可以用归纳方法证明。
如果数组arr里面有0个数或者1个数你该如何排序？答案是直接返回。
如果数组里有2个数呢？这个时候我们可以以arr[0]为基数，若arr[1]比arr[0]大则去arr[0]的右边，否则则去左边。
如果数组里有3个数呢？我们还可以以arr[0]为基数，比较剩余两个数与基数的大小。假设剩余两个数都比基数小，则需要对其进行排序，在上面我们已经实现了。
如果数组里有4个数呢？我们仍可以选取arr[0]为基数，让其余数据依次对齐进行比较。再假如，这次其余三个数都比arr[0]大，现在我们只需要重复上一步即可。
那5个呢？6个呢？7个呢？最极端的情况无非是都比基数大，或者比基数小，只需要重复上面的操作即可，一直到数组的长度为1或0时结束。
归纳证明分为两步：基线条件和归纳条件。假设我要证明我能爬到梯子的最上面。归纳条件是：如果我能现在第一个横杠上，我就能爬到第二个横杠上。基线条件是：我已经现在了第一个横杠上。是不是跟上面的很像！证明快排的归纳条件是：如果证明了对包含一个元素管用，那么对两个元素则管用。如果对两个元素管用，那么对三个元素也管用，以此类推。基线条件是：证明了这种算法对空或1个元素管用。
终于要到重点了
众所周知，理解了跟能否写下来代码是两回事。由于原书是Python，我就想着能不能找个go版本的，结果在看完这一章还真的在评论区看到一位兄弟发的go版本代码。简单的测试了一下，能跑！
过了一会遇到了一道需要时间复杂度小于O(nlog(n))的算法，我立马就想到了刚刚测试过的代码。由于还需要修改很多东西，我就一阵爆改，随之提交代码，结果一直不能完全通过。然后我研究了一上午…最终发现是那位兄弟的代码出了问题！！！他在快排的时候没有考虑数组内会有相等的情况，所以在排序的时候会漏掉一些数据！！！自始至终，我把自己改的代码怀疑了一个遍，最后甚至怀疑是编译器的问题都没有怀疑过那位兄弟的代码……
还是要谢谢那位兄弟，不然我现在对快排的印象也不会这么深。
网友评论