快速排序理解
快速排序算法核心思想，取待排序序列中的某个元素作为分区点，大于分区点的元素挪到分区点右边（从小到大排序），小于分区点的元素挪到分区点左边。然后分区点左右两边的子序列循环以上操作，直至子序列长度为 1。
左右指针法实现思路
1、首先定义分区点（pivot）p，p 一般为数组 a 的第一个元素或最后一个元素
2、然后定义左（l）、右（r）两个指针分别指向数组的第一个元素（a[0]）和最后一个元素 (a[a.length - 1])
3、如果 a[l] > a[p]，l、p 下标元素互换，l 前进 1 位
4、如果 a[r] < a[p]，r、p 下标元素互换，r 后退 1 位
5、如果 l >= r，排序结束
快速排序左右指针法图解过程
代码实现
以递归方式实现编码，首先找出分析出递归条件：
1、递归方程：quickSort(a[l..r]) = quickSort(a[l..p-1]) + quickSort(a[p+1..r])
2、递归退出条件：l >= r
注意点：如果选择分区点
p = l，必须先从右边找到小于a[p]的第一个元素开始
/**
* 快速排序
*
* @param a 待排序数组
* @param l 第一个元素下标
* @param r 最后一个元素下标
*/
public static void sort(int[] a, int l, int r) {
if (a == null || l >= r) {
return;
}
int i = l, j = r;
int p = l; // 选择最左边的元素为 pivot
while (l < r) {
// 如果选择 p = l 必须先从右边找到小于 a[p] 的第一个元素
while (l < r && a[r] >= a[p]) {
r--;
}
swap(a, r, p);
p = r;
// 从左边找到大于 a[p] 的第一个元素
while (l < r && a[l] <= a[p]) {
l++;
}
swap(a, l, p);
p = l;
System.out.println(Arrays.toString(a));
}
sort(a, i, p - 1);
sort(a, p + 1, j);
}
public static swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}