快速排序（Quick Sort）
快速排序由C. A. R. Hoare在1962年提出。
是对冒泡排序的一种改进，基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
思路分析
快速排序,说白了就是给基准数据找其正确索引位置的过程.
快速排序的思想就是，选一个数作为基数（这里我选的是第一个数），大于这个基数的放到右边，小于这个基数的放到左边，等于这个基数的数可以放到左边或右边，看自己习惯，这里我是放到了左边，一趟结束后，将基数放到中间分隔的位置，第二趟将数组从基数的位置分成两半，分割后的两个的数组继续重复以上步骤，选基数，将小数放在基数左边，将大数放到基数的右边，在分割数组，，，直到数组不能再分为止，排序结束。
例如从小到大排序:
- 第一趟，第一个数为基数temp，设置两个指针left = 0，right = n.length，
①从right开始与基数temp比较，如果n[right]>基数temp，则right指针向前移一位，继续与基数temp比较，直到不满足n[right]>基数temp
②将n[right]赋给n[left]
③从left开始与基数temp比较，如果n[left]<=基数temp，则left指针向后移一位，继续与基数temp比较，直到不满足n[left]<=基数temp
④将n[left]赋给n[rigth]
⑤重复①-④步，直到left==right结束，将基数temp赋给n[left] - 第二趟，将数组从中间分隔，每个数组再进行第1步的操作，然后再将分隔后的数组进行分隔再快排，
- 递归重复分隔快排，直到数组不能再分，也就是只剩下一个元素的时候，结束递归，排序完成
根据思路分析，第一趟的执行流程如下图所示：
动图展示
代码实现
public static void quickSort(int[] num,int left,int right){
//递归的出口
if(left>=right){
return;
}
//获取基准值所在的索引
int res = particular（num,left,right）;
//对左区间进行排序
quickSort(num,left,res-1);
//对右区间进行排序
quickSort(num,res+1,right);
}
public static int particular(int[] num,int left,int right){
//确定一個基准值，这里的基准值确定为最右边的数
int base = num[right];
while(left<right){
while(num[left]<base&&left<right){
left++;
}
if(left<right){
num[right]=num[left];
right--;
}
while(num[right]>base&&left<right){
right--;
}
if(left<right){
num[left]=num[right];
left++;
}
}
//循环结束
//此时left==right，而这个位置就是基准值在数组中应该在的位置
num[left]=base;
//最后返回基准值所在的位置
return left;
}
复杂度：
时间复杂度：O(nlogn)
- 最好情况（待排序列接近无序）时间复杂度为O(nlog2n)，最坏情况（待排序列接近有序）时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。
空间复杂度
- 空间复杂度：快速排序使用递归，递归使用栈，因此它的空间复杂度为O(logn)
稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法
