数据结构系列8
数据结构系列8-快速排序1(基本实现与弊端处理)
一：基本思想
快速排序它是一种基于二叉树结构的交换排序方法，其基本思想为：每趟排序时任意选取该趟序列中的某个元素(一般选择第一个或最后一个)作为基准元素，然后将整个序列划分为左右两个部分，其中左侧部分均小于基准元素，右侧部分均大于基准元素(升序)，然后对左右两个部分的序列继续执行上述操作。
其大致流程如下
二：代码
（1）单趟排序分析
(升序)
一般来说我们选择基准元素时选择的是第一个元素或最后一个元素，如果选择第一个元素，则一定先让end指针先走，这样才能保证他们相遇时是一个比key小的位置，因为最后一刻还要把这个begin和end同时指向的元素和第一个元素相交换，那么自然而然这一位的元素一定要比基准元素小。如果相反，那么反而还把大于基准的元素放到了第一个位置，这显然是不合适的。
(当然，如果选择最后一个元素，则一定要让begin指针先走，这样才能保证他们相遇时是一个比key大的位置.）
（2）完整排序
前面说过，快速排序是基于二叉树结构的一种交换排序方法。可以简单说，它实际是前序遍历过程，第一趟排序，划分为两个区间，第二趟排序去排左子树同时把左子树又划分两个区间，以此类推。
下面是堆排序代码，上述一趟排序结束后，让此函数返回begin的下标，然后分别对左子树和右子树进行快速排序，也就是递归
大致递归过程如下
每次排序划分区间后，通过特殊的方式进行输入，可以很清晰地看到这一个递归过程
（3）快速排序的弊端：小优化
前面说过简单插入排序不愿意遇见高度无序的序列，序列越有序它越快**，而快速排序越不愿意遇见高度有序的序列，序列越无序，越随机它越快**（相对于有序而言）
比如说下面这个序列已经有序了，如果使用快速排序，它将会发生下面的这种尴尬的情况（虽然这个序列已经有序了，但是使用快速排序之前并不知道）
可以发现，如果完全有序，那么每次划分时，只能舍去一个元素，对于剩余N-1个元素还要进行排序。先不要说时间复杂度，就是很小的数，如果是这样的情况，几次排序之后早就栈溢出了。
下面有两个有序数组，分别使用简单插入排序和快速排序测试
可以发现快速排序竟然比插入排序还要慢，这显然有点不合理。虽然这种情况很少见，但也足以暴露出快速排序的弊端所在
所以我们可以使用三数取中法进行优化，在每次排序时，调用一个函数取出下标为与开始，中间和结尾处的三个元素，然后比较，返回中间元素的下标，把中间元素与左侧元素进行交换，这样一来，咱们基准元素就不可能是一个序列中最小或最大，也就避免了这种不利的情况
（三数取中法）
依然使用刚才的数组进行测试，得到了明显的提高