快速排序（Quick Sort）

快速排序由C. A. R. Hoare在1962年提出。
是对冒泡排序的一种改进，基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。

思路分析

• 快速排序,说白了就是给基准数据找其正确索引位置的过程.

• 快速排序的思想就是，选一个数作为基数（这里我选的是第一个数），大于这个基数的放到右边，小于这个基数的放到左边，等于这个基数的数可以放到左边或右边，看自己习惯，这里我是放到了左边，一趟结束后，将基数放到中间分隔的位置，第二趟将数组从基数的位置分成两半，分割后的两个的数组继续重复以上步骤，选基数，将小数放在基数左边，将大数放到基数的右边，在分割数组，，，直到数组不能再分为止，排序结束。

例如从小到大排序:

1. 第一趟，第一个数为基数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]
2. 第二趟，将数组从中间分隔，每个数组再进行第1步的操作，然后再将分隔后的数组进行分隔再快排，
3. 递归重复分隔快排，直到数组不能再分，也就是只剩下一个元素的时候，结束递归，排序完成

根据思路分析，第一趟的执行流程如下图所示：

动图展示

代码实现

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)
  稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法