快速排序
原理： 快速排序使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
1.挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）；
2.分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；
3.递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。因此快速排序属于不稳定排序。
对基准值选择对排序带来的影响，大家可以参考我自己写的一套OC代码实现，这个Demo中对比了三大基本排序和快速排序的效率，快速排序也支持选取第一个或最后一个或中间位为基准值。同学们可以手动设置数据源，对比一下这几种排序的效率，也可以观察不同基准值的快速排序效率上的差异。
快速排序的实现代码：
在前面我们知道，选取正确的基准值对排序的性能有着决定性的影响，在这里我们选择序列中间的值作为基准值。
代码主要分为两个部分：进行切分的代码和进行递归调用的代码
第一部分 进行切分
/**
* 进行切分，并进行交换
* @param a 数组
* @param lo 切分开始的位置
* @param h 切分结束的位置
* @return 返回分界点的位置
*/
public static int partition(int[] a,int lo,int h){
// 选取中间的值为基准值
int middle = (lo+h+1)/2;
int v = a[middle];
// 将基准值和a[lo]交换位置
exc(a, lo, middle);
int i = lo;
int j = h+1;
while(true){
// 假如左边的小于基准值，则一直进行循环
while(a[++i] < v){
// 防止越界
if(i == h){
break;
}
}
// 假如右边的大于基准值，则一直进行循环
while(a[--j]>v){
if(j == lo){
break;
}
}
// 一旦i>=j则代表i前面的除第一个外都比基准值小，j后面的都比基准值大，这时候就可以跳出循环了
if(i>=j){
break;
}
// 进行交换(因为a[lo]>v,a[h]<v，所以将两者进行交换)
exc(a, i,j);
}
// 将基准放到分界点
exc(a, lo, j);
return j;
}
第二部分 进行递归调用
/**
* 调用quickSort函数
* @param a 数组
*/
public static void quickSort(int[] a){
quickSort(a,0,a.length-1);
}
/**
* 进行递归的快排
* @param a
* @param lo
* @param h
*/
public static void quickSort(int[] a,int lo,int h){
if(h <= lo) {
return ;
}
// j为基准值的位置
int j = partition(a, lo, h);
// 进行递归调用，将j前面的进行快排
quickSort(a,lo,j-1);
// 进行递归调用，将j后面的进行快排
quickSort(a,j+1,h);
}
快速排序
特点：
快速排序在最坏的情况下时间复杂度是O(n**2),平均时间复杂度是O(nlogn)。快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。
出处：https://www.cnblogs.com/xiaohuiduan/p/11188304.html
GitHub代码为原创
