快速排序
快速排序思想
1962年，由C.A.R.Hoare创造出来。该算法核心思想就一句话：“排序数组时，将数组分成两个小部分，然后对它们递归排序”。然而采取什么样的策略将数组分成两个部分是关键，想想看，如果随便将数组A分成A1和A2两个小部分，即便分别将A1和A2排好序，那么A1和A2重新组合成A时仍然是无序的。所以，我们可以在数组中找一个值，称为key值，我们在把数组A分解为A1和A2前先对A做一些处理，让小于key值的元素都移到其左边，所有大于key值的元素都移到其右边。这样递归排序A1和A2，数组A就排好了。
举例
我们要排序的数组如下：
55 41 59 26 53 58 97 93
我们选取第一个元素作为key值，即55.（一般都是选取第一个元素）。假如我们有一种办法可以将数组做一步预处理，让小于key值的元素都位于其左边，大于key值的元素都位于其右边，预处理完数组如下：
41 26 53 55 59 58 97 93
这样数组就被key值划分成了两段，A[0...2]小于key，A[4...7]大于key，可见key值本身已排好序，接下来对A[0...2]和A[4...7]分别进行递归排序，那么整个数组就排好序了。预处理做的工作再次澄清下：找一个key值，把key位放到某位置A[p]，使小于key值的元素都位于A[p]左边，大于key值的元素都位于A[p]的右边。到此，我们的快排模型就成型了。
/*l, u 代表待排序部分的下界和上界*/
void qsort(l, u)
{
/*递归结束条件是待排序部分的元素个数小于2*/
if(l >= u)
{
return;
}
/*此处进行预处理，预处理后key值位于位置p*/
qsort(l, p-1);
qsort(p+1, u);
}
接下来看如何做预处理。我们选取A[0]做为key值, p作为key值的位置。我们从A[1]开始遍历后面的数组，用变量i指示目前的位置，每次找到小于key的值都与A[++p]交换。开始时p=0.
55 41 59 26 53 58 97 93 i = 1，A[i]位置为41, 即A[i] < key, swap(++p , i)，即p = 1:
55 41 59 26 53 58 97 93 i = 2，A[i]位置为59，A[i] > key，不做任何改变。
i = 3，A[i]位置为26，A[i] < key，swap(++p, i)， 即p = 2:
