重生之我在黑盒学编程4

今天我们来学点算法——快速排序算法

快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用（应该是吧），他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。

下面‘简单’的讲解一下

比如将一个数组的起始位置记成left，最后一个元素位置记成right，那么标记left的位置的元素，把该元素看成基准点

这时候right要不断的向左移动，若right所在位置的元素是小于key位置的元素，那么right停止移动。left要不断的向右移动，若left所在位置的元素是大于key位置的元素，那么left停止移动。总结就是：left找大，right找小。

注：思路来自csdn

简单推导一下得到上图。

你如果觉得这个方法太难，没关系还有一个更难的方法

和上一个方法一样先定义一个基准点，只不过把这个基准点叫做“坑”，“坑”里的元素是要被抹除的（也就是“坑”里不能有元素），因此先用一个变量key来保存“坑”里的元素。right向左移动找到小于该基准点（“坑”）的元素就把这个元素填到“坑”里，这时候“坑”里有了元素，可以表示“坑”被填满了，但是right位置的就变成了新的“坑”，因为right位置的元素被用来“填坑”了。

下一次就是left找大的元素给到right位置的”坑“，然后left的位置就成了新坑，如此反复，直到left和righ相遇，待到他们相遇的位置必然是一个”坑“，这时候把key存储的元素放到这个”坑“里，此时会发现数组也以5（key）为中心点分成了两个区间，而且左区间的元素都是小于key的，右区间的元素都是大于key的。