参考博文：

快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现

　　思想：

　　　　1.在待排序的元素中任取一个元素作为基准（通常选第一个元素，但最好的选择方法是从待排序元素中随机选取一个作为基准），称为基准元素

　　　　2.将待排序的元素进行分区，对基准元素大的元素放到它的右边，比其小的放在它的左边

　　　　3.对左右两个分区重复以上步骤直到所有元素都是有序的

　　所以可以把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态，

　　左边被拆了，就要遍历右边的元素去补，右边被拆了，就遍历左边的元素去补

　　实现代码：

1 public class QuickSort { 2      3     public static void main(String[] args) { 4         int[] arr = {5,7,1,8,4}; 5         int _left = 0; 6         int _right = arr.length-1; 7          8         System.out.print("排序前：" ); 9         for(int num:arr) {10             System.out.print(num);11         }12         13         quickSort(arr,_left,_right);14         System.out.print("----排序后：" );15         for(int num:arr) {16             System.out.print(num);17         }18     }19 20     private static void quickSort(int[] arr, int _left, int _right) {21         int left = _left;22         int right = _right;23         int base = 0;24         if(left < right) {25             base = arr[left];                //我们将base元素单独拿出，这样base元素的位置就出现了一个坑26             while(left != right) {27                 while(left < right && arr[right] >= base)         //从右往左找 小于 base 的元素，将其填入base左边的坑中28                     right--;                                    //这个 while的目的，就是不停地移动right指针，直到某个元素小于base，29                 arr[left] = arr[right];                            //小于base的元素是不应该出在右边的，所以我们把它放到左边的坑中，这样在右边又空出来了一个坑30                 31                 while(left < right && arr[left] <= base)        //从左往右找 大于 base 的元素，将其填入base右边的坑中，while的目的和上面类似        32                     left++;                                        //用左边大于base的元素填充右边的坑，33                 arr[right] = arr[left];34             }35             36             arr[right] = base;        //将基准值回归填充到中间37             38             quickSort(arr,_left,left - 1);    //对基准元素左边的元素递归排序39             quickSort(arr,right + 1,_right);//对基准元素右边的元素递归排序40         }41     }42 }