快速排序算法详解（小白都能看懂的白话文）

快速排序的排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。

快速排序的基本思想是：通过一次将需要排序的数据分为两部分，一部分是的数都比另一部分的数大，再按这种方法对这两部分数据分别在用快速排序的方法，整个排序过程可以递归进行，使整个数据变成有序序列。（这里看不懂，不急）

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。为了方便理解，将快速排序的思想简化成挖坑填坑+分治。

下面以一个数组a[10]为例：

首先我们需要先选取一个X(基准数)，这个基准数我们可以选取数组的第一个元素或者最后一个元素，也可以选取中间的元素。这里我们选取第一个元素a[0]，同时设头(i=0),尾(j=9),然后把a[0]赋值给X，这里就相当于在a[0]的位置挖了一个坑🕳，这时候我们要从后往前(j--)找一个比X小或者等于X的数，然后把找到的这个数挖出来填到我们之前挖的坑里面，当j=8时，符合条件，把a[8]赋值给a[0]，并且i++，这时候我们填上了一个坑，又出现了另一个坑a[8],这时我们需要从前往后(i++)去找一个比X大的数去填这个坑🕳，当i=3时，符合条件，把a[3]挖出来赋值给a[8]，并且j--。

在重复上面的操作，先从后往前找一个比X小或者等于的数，然后把这个数挖出来去填坑，在从前往后找一个比X大的数去填坑....

从后往前：当j=5时，符合条件，a[3]=a[5],i++;

从后往前：当i=5时，由于i==j退出，这时a[5]是我们需要填的坑

此时，i=j=5，我们只需要把X这个数填到a[5]这个坑🕳里面即可。

从上面的图片我们可以看出，在a[5]左边的数都是比它小或者等于它的数，右边的数都是比它大的数，这时候我们就完成了一次排序，紧接着我们在对a[0]--a[4]和a[6]--a[9]分别再次重复上述步骤。

这里以a[0]--a[4]为例：设基准数X=49（随便哪个都行），i=0,j=4

对挖坑填数进行总结:

1．i 为头; j 为尾; 将基准数X挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，最后将基准数填入a[i]中。

根据上面的思路

我们先来写挖坑填坑的代码：

然后通过递归来实现分治：

把上面两部分合起来得到快速排序的代码：

有的书上是以中间的数作为基准数的，这样实现也非常方便，直接将中间的数和第一个数进行交换就可以了。Swap(s[l], s[(l + r) / 2])

快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)。

最后我们来验证下代码：

没问题，下机，结束。。。。。。。。。。