前言：
大家好，这是0基础学算法的第一课，当然这个0基础并不是我们常规意义上的0基础，你需要掌握一点语法知识即可学习此课程，夸张点说会敲“Hello World”就行/doge。当然这是一个系列课，我将由简到深的为大家讲解一些算法知识，从排序到搜索以及更多，也希望这个系列可以给你带来帮助。算法学习是个很难的过程，希望你可以在此过程中坚持下来，加油！
附：系列中出现较难的知识点或者语法知识我都会作讲解，如果还有什么不明白的知识可以在下方评论，本人看到后会立即回复滴。
知识讲解：
下面直接开始我们今天所要讲解的知识——快速排序。
快速排序重要性：
快速排序是我们在编程技术中十分常见的一种排序方式，其由于排序效率在同为O(N*logN)的几种排序方法中效率较高，所以经常会被采用，再加上处理快速排序时使用的分治法思想十分实用，这就导致了很多的软件公司（腾讯，微软等知名IT公司）在笔试面试的时候也会很喜欢考这个，还有我们在程序方面的考试（软考等）和一些比赛（PAT，蓝桥杯等）还有考研中都会经常出现他的身影。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。我们在实现快速排序的时候会采用一种分治的策略，也成为分治法(Divide-and-ConquerMethod)。
分治法的基本思想：
分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
实现步骤：
在我们今天学习的算法中，我们将其分为以下的三个步骤：
1．先从数列中取出一个数作为基准数。（确认边界点）
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。（重新调整区间）
3．再对左右区间重复第二步，直到各区间只有一个数。（递归）
看完上面你也不妨看出我将其简化为：确认边界点-重新调整区间-进行递归。三个步骤去进行实现。在这三个步骤中，要注意的一点是:在进行确认边界点的时候我们要考虑确定的边界点是左边界？右边界？中点？随机？的同时也要考虑取哪个点更方便我们后续的操作。
如上文所说，我们在分区选点的时候会面临着四种选择，在这里我们选择取中间点为我们的分界点，在这里会有人问为什么不取其他的点呢，先说随机点，这个就相对来说比较麻烦，然后左右两个端点为什么不建议取呢，主要是左右两个端点与后面开区间时会有边界值无法通过的现象，我们在举出特殊例子时是可以看出的，在这里我就不为大家列举了，这个知识相对来说没那么重要，我们只需记得取中间点为分界点即可。
在经过第一步的思考后我们在进行分区的操作是也如下图所示：
快速排序分区过程实现简图
到这里我们距离实现快速排序也只差了一步，也就是我们的递归，这个递归就是我们就是不断分界，分到最小单元。（当然这个现在看不懂没关系，到后面的代码展示环节时会出现）
举例：
我为大家举一个实例来帮助大家理解。以一个数组作为示例，取区间中间数数为基准数（标红）。
数组
然后我们将左右两个端点的下标记住，
之后的我们就将左右两个元素交换，交换后继续重复上述操作，直到两个指针相遇停止，也就是如下操作：
交换位置：
之后继续移动直到相遇：
相遇的时候对应下标为：4 。这个时候明显可见我们数组中0-4的数字都是<=85的，而5-9的数字都是>85的。
所以我们就将数组一分为二(并不是真正意义上的分开），0-4分开进行排序，5-9分开进行排序。
排序的过程也就跟我们上面所描述的一样。
数组
0 1 2 3 4 5 6 7 8 9
82 24 73 71 85 94 88 90 86 93
相信聪明的各位已经看出来了，这里的一分为二就是在同一个数组上分开两次进行上述方法的交换。交换的具体过程我就不细写啦，结果如下：
数组
0 1 2 3 4 5 6 7 8 9
71 24 73 82 85 86 88 90 94 93
然后继续套娃，分开进行：
数组
0 1 2 3 4 5 6 7 8 9
71 24 73 82 85 86 88 90 94 93
数组
0 1 2 3 4 5 6 7 8 9
24 71 73 82 85 86 88 90 93 94
显而易见到这里我们的排序就完成啦，也成功的对这个数组进行了一次排序。
思路：
思路就是对上面步骤以及例子的总结。我之所以放到例子后面附上主要是希望大家通过看例子可以加深对这些的记忆。在这里我直接为大家附上图，希望大家更容易理解一些。
思路一：
思路一就是我们的暴力解法，直接开两个数组，然后找出分界点，将比分界点小以及大的数字分别放入两个数组，最后再归还为原数组。
思路二：
在这里思路二也就是我们上面举例子用的方法，也是我们今天主讲的思路，就是用双指针进行不断靠近。
快速排序实现：
在这里快速排序的实现我就为大家简化为下面几步：
第一步：开一个数组
第二步：输入元素个数
第三步：将每个元素输入
第四步：调用模板
非常的通俗易懂是吧，在这里大家都想知道这个模板是什么，所以我们的重头戏就来了！
模板：
模板的实现我给大家已画图的方式列出，字丑希望大家不要介意。
在这里你可能会疑惑，哎?这不就是刚才讲的那些内容吗，为什么还要再说一遍呢?
我之所以在这里再提到一遍，主要是因为在我们学算法刷题时，不是说只学那个方法就可以了，我们有很多要考虑的东西，有的边缘值了，范围了都需要我们考虑。就比如刚才模板中的1个数不用排序的情况，如果我只给你讲解了前面的知识，你可能会理解快速排序，但是你自己实现起来会有很大的难度，有很多是你很难想象的到的错误，所以大家不要嫌我讲的繁琐。/抱拳
模板的代码实现：
void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1 ; int j = r + 1 ; int x = q[l + r >> 1] ; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) { swap(q[i], q[j]); } } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
好了，到了这里肯定有hxd会问：l+r>>1是什么意思。我在这直接为大家讲一下:
这里>> 就是二进制右移运算符。将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。
简单点来说 x>>1等价于x/2 。
为了方便大家学习，我直接把这两个公式给大家附上，希望大家可以看一下：
· x >> n 等同于 x / (2^n) ，x << n 等同于 x * (2^n)
实战
到这里大家对快速排序已经了解的差不多了，下面看几个简单的题目来巩固一下吧。
