一、快速排序算法：划分是问题的关键。
1.分解：将数组划分为两个数组，使得一个数居中，左侧都小于等于他，右侧都大于等于他。其中计算中间数下标也是划分过程的一部分。
2.解决：通过递归调用快速排序，对于子数组（左右数组）进行排序。
3.合并：因为子数组都是原址排序的，所以整体数组已经有序。
伪代码：
QuickSort(A,p,r)
if(p<r)
q=partition(A,p,r)//得到中间元素的下标
QuickSort(A,p,q-1)
QuickSort(A,q+1,r)
二、快排之单向扫描分区法
-一遍扫描法的思想是，用两个指针将数组划分为三个区间。
-扫描指针sp-(scan_pos)：左边是确认小于等于主元的。
-未知区间末指针bp-(next_bigger_pos):末指针的右边区间为确认大于主元的元素。扫描指针到某个指针(next_bigger_pos)中间为未知的。
<=sp 右移
> 交换并bp左移
边界：如果最后一个扫描元素大于主元，bp左移之后小于了sp
如果最后一个扫描的元素小于主元，sp的右移导致，sp大于bp
伪代码：
//单项扫描分区法
partition(A,p,r)：
pivot=A[p];//主元
sp=p+1;//扫描指针
bp=r;//右侧指针
while(sp<bp){
if(sp<=pivot)//扫描指针小于主元，扫描指针右移
sp++;
else
swap(A,sp,bp);//扫描指针大于主元，两指针的元素交换，右侧指针左移
bp--;
}
swap(A,p,bp);
return bp;
import java.util.Arrays;
public class 快排之单向扫描分区法 {
public static void main(String[] args) {
int arr[]=getRandomArr(10,1,20);
System.out.println("原数组："+Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("排序后："+Arrays.toString(arr));
}
public static void quickSort(int[]A,int p,int r) {
if(p<r) {
int q=partition(A,p,r);
quickSort(A,p,q-1);
quickSort(A,q+1,r);
}
}
//单项扫描分区法
public static int partition(int[] A, int p, int r) {
int pivot=A[p];//主元
int sp=p+1;//扫描指针
int bp=r;//右侧指针
while(sp<=bp) {
if(A[sp]<=pivot)//扫描元素小于等于主元，扫描指针右移
sp++;
else {
swap(A,sp,bp);//扫描元素大于主元，两指针元素交换，右指针左移
bp--;
}
}
swap(A,p,bp);
return bp;
}
//获取随机数组
public static int[] getRandomArr(int length, int min, int max) {
int arr[]=new int[length];
for(int i=0;i<length;i++) {
/*Math.random()能够产生[0,1)的浮点数。
* 返回给定范围的随机整数
* Math.random()*(最大数-最小数+1)+最小数*/
arr[i]=(int)(Math.random()*(max-min+1)+min);
}
return arr;
}
// 在数组内原址交换元素
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
三、 快排之双向扫描分区法
双向扫描的思路是，头尾指针往中间扫描，从左找到大于主元的元素，从右找到小于等于主元的元素
二者交换，继续扫描，直到左侧无大元素，右侧无小元素。左先右后。
伪代码：
//双向扫描法
partition2(A,p,r){
pivate=A[p];//主元定为第一元素
left=p+1;//第二个元素
right=r;//最后一个元素
while(left<=right){
//left不停往右走，直到遇到大于主元的元素
//循环退出时，left一定是指向第一个大于主元的位置
while(left<=right&&A[left]<=pivot) left++;
//循环退出时，right一定是指向最后一个小于等于主元的位置
while(left<=right&&A[left]>pivot) right--;
//left指针与right指针交换
if(left<right)//等于交换没有意义
swap(A,left,right);
}
//while退出时，两者交错，且right指向的是最后一个小于等于主元的位置，也就是主元应该是待的位置。
swap(A,p,right);
return right;
}
import java.util.Arrays;
public class 快排之双向扫描分区法 {
public static void main(String[] args) {
int arr[]=getRandomArr(10,1,20);
System.out.println(Arrays.toString(arr));
quickSort2(arr,0,arr.length-1);//双向扫描分区法
System.out.println(Arrays.toString(arr));
}
//双向扫描分区法
public static void quickSort2(int[]A,int p,int r) {
if(p<r) {
int q=partition2(A,p,r);
quickSort2(A,p,q-1);
quickSort2(A,q+1,r);
}
}
public static int partition2(int[] A, int p, int r) {
//三点中值法优化主元
int midIndex=(r+p)/2;
int midIndexValue=-1;
if(A[p]<=midIndexValue&&A[p]>A[r]){
midIndexValue=p;
}else if(A[r]<=midIndexValue&&A[r]>A[p]){
midIndexValue=r;
}else{
midIndexValue=midIndex;
}
swap(A,p,midIndexValue);
int pivate=A[p];//主元一般定为首元素
int left=p+1;//第二个元素
int right=r;//最后一个元素
while(left<=right){
//left不停往右走，直到遇到大于主元的元素
//循环退出时，left一定是指向第一个大于主元的位置
while(left<=right&&A[left]<=pivate) left++;
//循环退出时，right一定是指向最后一个小于等于主元的位置
while(left<=right&&A[right]>pivate) right--;
if(left<right)
swap(A,left,right);
}
//while退出时，两者交错，且right指向的是最后一个小于等于主元的位置，
//也就是主元应该是待的位置。
swap(A,p,right);
return right;
}
//获取指定范围指定个数的随机数组成的数组
public static int[] getRandomArr(int length, int min, int max) {
int[] arr = new int[length];
for (int i = 0; i < length; i++) {
arr[i] = (int) (Math.random() * (max + 1 - min) + min);
}
return arr;
}
// 在数组内原址交换元素
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
三、 快排在工程实践中的优化
１．三点中值法优化主元－－－－在p,r,mid之间，选一个中间值作为主元。
２．绝对中值法
３．待排序列表较短时，用插入排序 | 
转播
