快速排序传说中很imba的一种排序。
快速排序大概步骤是三部曲
第一部：选主源
第二部：子集划分
第三部：算法实现
这三部曲讲的就是，假设你有个数组之类的数据源。
就想上图中左边这样，一个无序的数据源，那先要选出一个锚点，或者叫pivot，然后像上图中右边这样，以锚点为中心，比锚点大的放左边儿，比锚点小的放右边儿。这样就完成了第一轮儿快排。
那么先来讲下第一部的故事。
讲的就是这个锚点啊就是pivot选择实际上至关重要，一般就是取三个数，数据源头，尾，和中间的数，然后比较一番。给三个人先做个简单的排序，从小到大那样，如图
这里的伪码描述的就是一个选择pivot的过程，就是三个if把三个数进行从左到右，从大到小的排序，并且放回到数据源中。这个swap就是交换的意思。
他这个最后一步要解释下，我在别人的算法中没怎么看过这么做，不过浙大这个课程还是很科学的，他的意思就是你可以直接把数据源中下标为0，Length-1,Length-2这三个位置先忽略了，为啥呢，因为这仨位置实际上就是刚刚选主源挑出来的数，然后最后一步的交换也是把pviot本应该再数据源中间位置的数，交换到倒数第二位，为了让后面写快排代码时候，循环不必还要特意跳过中间位置。
这张图说明的就是一个快排算法里循环到底在干啥，可以看到最右面红色的6就是找好的pivot并且已经交换到数据源倒数第二个位置，这样设置两个下标，i和j，分别从左向右，还有从右向左扫描，i意味着第一张图的左边，j意味着第一张图里的右边。
这样每一次循环i和j分别和pivot比较一番，如果i位置的数比pivot大，先标记好暂停i的移动，看下j，j也要和pivot比较。如果比pivot大j继续移动，直到j碰到一个数比pivot小，那么说明j和i的数是需要调换下。以此类推，完成一轮快排。
最后就是递归的调用整个快排的过程。毕竟我们看第一张图可以看到，一轮儿快排做完也只是很粗略的排序，第一张图左边的数据还是不顺序的，所以每次递归就相当于重新挑选个pivot，只不过当量选择在左边儿那个堆数据里就可以。
下面是浙大课程里的伪码
在网上看到一个老哥写的java快排，写的很不错
/**
* 一次快速排序
* @param array 数组
* @param lo 数组的前下标
* @param hi 数组的后下标
* @return key的下标index，也就是分片的间 隔点
*/
public static int partition(int []array,int lo,int hi){
/** 固定的切分方式 */
int key=array[lo];//选取了基准点
while(lo<hi){
//从后半部分向前扫描
while(array[hi]>=key&&hi>lo){
hi--;
}
array[lo]=array[hi];
//从前半部分向后扫描
while(array[lo]<=key&&hi>lo){
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;//最后把基准存入
return hi;
}
/**
* 快速排序
* @param array
* @param lo
* @param hi
*/
public static void quickSort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
//进行第一轮排序获取分割点
int index=partition(array,lo,hi);
//排序前半部分
quickSort(array, lo, index - 1);
//排序后半部分
quickSort(array,index+1,hi);
}
//测试函数
public static void main(String[] args) {
int[] arr = {1,9,3,12,7,8,3,4,65,22};
quickSort(arr, 0, arr.length-1);
for(int i:arr){
System.out.print(i+",");
}
}
//三数取中
//下面的两步保证了array[hi]是最大的；
int mid=lo+(hi-lo)/2;
if(array[mid]>array[hi]){
swap(array[mid],array[hi]);
}
if(array[lo]>array[hi]){
swap(array[lo],array[hi]);
}
//接下来只用比较array[lo]和array[mid]，让较小的在array[lo]位置就OK。
if(array[mid]>array[lo]){
swap(array[mid],array[lo]);
}
int key=array[lo];
这个老哥的取pivot里就没有把pivot放最后，而是创建了变量key
最后浙大这个课程老师说快排还是适合大数据量，比如数据源大于几百以上，毕竟是递归的，还是挺吃内存。
