【算法】手撕快排

（分治法）快速排序思路：

1. 从目标数组中挑出一个基准值。

2. 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。

3. 递归基准值左边和右边，重复1，2步骤，直至排序完成。

   public class QuickSort { 
   public static void quickSort(int[] a, int l, int r) {
    /*l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
     *r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     *a -- 待排序的数组
    */
       if (l < r) {
           int i,j,x;
   
           i = l;
           j = r;
           x = a[i];
           while (i < j) {
               while(i < j && a[j] > x)
                   j--; // 从右向左找第一个小于x的数
               if(i < j)
                   a[i++] = a[j];
               while(i < j && a[i] < x)
                   i++; // 从左向右找第一个大于x的数
               if(i < j)
                   a[j--] = a[i];
           }
           a[i] = x;
           quickSort(a, l, i-1); //递归
           quickSort(a, i+1, r); 
       }
   }
   }
   

```