算法——快速排序

有人甚至将快排称为分治法，但分治更多应该指明是一种思想，而非具体的排序算法。
对于快速排序的内容，我这样概括：每趟排序将一个基准点归位，并且将原序列依照基准点分为两个部分。

实例

对于下面的序列：

{72,6,57,88,60,42,83,73,48,85}

我们来执行第一趟快排，以第一个元素72为基准点，将low指针也指向72，high指针指向85。我们开始第一趟快排，想象high指针从右侧第一个元素开始往左侧移动，当元素不在大于72时，也就是high指针指向48时，将48换到low指针指向的位置，也就是72元素的位置。此时有两个元素确定了与基准点元素的大小关系了（85,48）。
序列变为:

{48,6,57,88,60,42,83,73,48,85}

与刚刚相反，我们将low指针开始朝右侧移动，看元素是否小于基准点的元素，low指针跑到88时，会发现此时不再小于72了。则将此元素换到右侧high指针指向的位置。
序列变为:

{48,6,57,88,60,42,83,73,88,85}

类似的，再转换指针，让high指针从右侧往左侧走，73大于72,83大于72,但到了42就不满足条件了，我们将它换到左侧low指针指向的位置（留意到不会发生元素覆盖的现象，因为low指针指向的元素已经被换到了右侧）。
序列变为:

{48,6,57,42,60,42,83,73,88,85}

你可能也知道了，再将low指针从左往右走，42自然小于72，60小于72，又出现了一个42，但此时由于low和high指向了同一个位置，循环结束了。其实还不算完，我们还需要将这个位置上的值换为基准点的值。
序列变为:

{48,6,57,42,60,72,83,73,88,85}

我们会发现，一趟快排后，此时整个元素被72分为了两个子序列，左侧小于72，右侧大于72。
有人说这其实有些像填坑，我们就按照他们说的再来一趟：

0：{72,6,57,88,60,42,83,73,48,85}
1：{48,6,57,88,60,42,83,73,__,85} 
85和48已经排序完成，确定了他们在基准点的左侧还是右侧。
2：{48,6,57,__,60,42,83,73,88,85} 
88大于72了，将它丢到右侧去填坑，原位置留坑。此时85,48,6,57,88也已经确定关于基准点的位置了。
3：{48,6,57,42,60,__,83,73,88,85}
转换指针，high从右朝左走，到42发现小于72，将它丢入左侧填坑， 85,48,6,57,88,73,83,42均已经确定了关于基准点的位置了。
4：{48,6,57,42,60,__,83,73,88,85}
此时已经非常直观了，我们会发现仅60没有确认关于基准点的位置，我们转换指针，low指针从左朝右走，扫过60，发现不需要转换，之后达到high指向的位置，两个指针重合了。
5：{48,6,57,42,60,72,83,73,88,85}
将最后一个坑补上基准元素。

我们回顾一下，对于这趟排序，我们将n-1个元素与基准点元素做了对比，移动了若干个元素（具体几个目前不需要关注，但它一定小于n-1），将它们归置到想对基准点元素来说合适的一侧。
之后我们要做个，就是将基准点元素两个的部分，分别进行快排。每次快排确定一个基准点元素的位置，将原序列分为两个部分，如此往复，直到边界条件。

分析性能

对于快排，比较痛苦的事情就是分析它的性能，我们分别看它的最好情况，最坏情况，以及空间方面的内容。

最好情况

对于快排来说，本质上就是在分治，每次递归，将一个基准点元素归位，同时将基准点元素作为分割点，将原序列分为两个部分，一侧大于基准点，一侧则小于。
若每次递归基准点两侧分割都是均匀的，对于具有16个元素的序列来说，
第一趟快排，{16}需要做15次比较，若干次换位。
第二趟快排，{7}{8}需要做6+7=13次比较。
第三趟快排，{3}{3}{3}{4}需要做2+2+2+4=10次比较。
第四趟快排，{1}{1}{1}{1}{1}{1}{1}{2}需要做1次比较。
此时整个快排就结束了。
说起来，如果说每次递归都可以将原序列分为两个均匀的部分，则一共要进行log2(n+1)（取上界值）此递归，再这么多次递归过程中，每趟比较n-2^n+1次，通过指数递减的方式做到——最后一趟时仅仅发生一次比较。
以上就是快排的最好情况。

最坏情况

依然通过快速排序的原理来分析。
对于最好情况，我们进行log2(n+1)（取上界值）次递归，对于最坏情况，我们让递归次数达到最大，每趟递归所需要比较的次数也达到最大。自然就是最坏情况了。
{1,2,3,4,5}
第一趟：比较5-1=4个元素
第二趟：比较5-2=3个元素
第三趟：比较5-3=2个元素
第四趟：比较5-4=1个元素
其实想象一下，这时的情况类似于一颗右偏的二叉树，每个结点仅有右子节点的那种。
当逆序的时候，其实类似。