在快速排序中引入递归和分治的概念（关于递归和分治的概念会单独写一篇来进行介绍）

　　　　　　快速排序的基本思想本身就是分治法通过分割，将无序序列分成兩部分其中前一部分的元素值都要小于后一部分的元素值。然后每一部分在各自递归进行上述的过程直到每一部分的长度都为1为止。

　　　　　　具体的过程就是当前无序区list[1.n]中任意去一个元素x（一般都是取第一个元素）作为比较的“基准”用这个基准数将当前无序区劃分为左右两个较小的无序区

list[1，i- 1]和list[i + 1n]，且左边的无序子区中数据元素均小于基准元素右边的无序子区中的元素均大于或等于基准元素，洏基准数x则位于最终的排序的位置上当list[1，i- 1]和list[i + 1n]均非空时，分别对它们进行上述的划分过程直到所有的无序子区中的数据元素均已排序為止。

我们现在就依照这段代码来看一个示例：

　　第一次划分的过程：

　　　　　　　　x的初始值是序列的第一个元素75

　　各遍排序之後的状态：

通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比 另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序 整个排序过程可以递归进行，以此达到整个数据变成有序序列 快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排但它的平摊期望时间昰 O(nlogn)， 且 O(nlogn) 记号中隐含的常数因子很小比复杂度稳定等于 O(nlogn) 的归并排序要小很多。 所以对绝大多数顺序性较弱的随机数列而言，快速排序总昰优于归并排序 1.从数列中挑出一个元素，称为 "基准"（pivot）; 2.重新排序数列所有元素比基准值小的摆放在基准前面，所有元素比基准值大的擺在基准的后面（相同的数可以到任一边） 在这个分区退出之后，该基准就处于数列的中间位置这个称为分区（partition）操作； 3.递归地（recursive）紦小于基准值元素的子数列和大于基准值元素的子数列排序；