快速排序

最近找实习，发现快排挺吃香的，昨天阿里的面试官问了快排的思想和收敛条件，今天做另一家公司的笔试题也让写实现快速排序的函数，从思想到代码实现，还是得总结一下，只有真正理解了，才记的更牢，运用的更灵活。

在了解快速排序的思想和性能之前，先了解一下快排的基本实现过程。

1.从待排序的数据序列中任取一个数据作为分界值，所有比它小的元素都放在左边，所有比它大的元素都放在右边，这样就形成了两个子序列。

2.对上一步形成的两个子序列分别进行递归排序，直到每个子序列中的元素只有一个，排序完成。

算法思路：

1）选择一个分界值，这里可以选择序列最左端的值

2）定义一个变量i，i从序列的左端开始向右扫描，找到大于分界值的索引，并用 i 记录该索引；

3）定义一个变量j，j从序列的右端开始向左扫描，找到小于分界值的索引，并用 j 记录该索引；

4）如果i < j，交换 i , j 索引位置两元素的值

5）重复执行前2,3,4步骤，直到i >= j ，此时 j 左边的元素都比分界值小，j 右边的元素都比分界值大,将分界值与 j 处的元素交换（这里选 j 是因为先从左边找，再从右边找，再判断 i , j 的关系，所以 j 找完了之后已经达到分界要求了） 

6）之后得到两个子序列即分界值左边的序列和分界值右边的序列，然后对子序列分别再进行1,2,3,4,5的排序，直到每个子序列中只有一个元素（即待排序的序列左端的下标>=右端的下标），排序完成。

java代码如下：

思想：分治思想

第一步：分解  数组A [ p. .r ] 被划分为两个（可能为空）子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于A[q]，而A[q]也小于A[q+1..r]中的每个元素。（分区、数组划分）

第二步：解决  递归调用快速排序，对数组A[p..q-1]和A[q+1..r]进行排序

第三步：合并  子数组基于原址排序，A[p..r]已有序，不必进行合并。

初始调用：quickSort(A,0,A.Length-1)

递归收敛条件：子数组中只剩一个元素

性能：

依赖于划分是否平衡，而平衡又依赖用于划分的元素

最坏情况划分：每次递归调用了这种不平衡划分（两个子问题分别包含了n-1个元素和0个元素）  O（n*n）

最好情况划分：分区后得到两个子问题规模都不大于n/2   n lg n

平衡划分：快速排序的平均运行时间接近于最好情况

优化：随机化划分的元素(平衡划分)       pivot = RANDOM(p,r)