排序1-快速排序

时间复杂度：O(n*logn)，logn是使用分治提高了效率，缺点是越接近有序效率越低，会退化到O(n^2)

　　　　　　我的实现代码经实测，100万长度数组排序时间平均约为160毫秒

基本思路：

　　1.基准 对数组选取一个基准数（通常第一个数，提高效率可以取中间的数）

　　2.分区 依次比较替换后将数组分为两部分，在基准数位置之前的全部小于基准数，之后的全部大于基准数

　　3.递归 对基准数左右两部分子数组递归使用同样的分区方法，直到所有数都确定位置

我的代码实现：

　　使用了效率较高的两路快排（亦称填坑法），一个指针从前向后寻找第一个大于基准数的位置，另一个指针从后向前寻找第一个小于基准数的位置，找到后交换位置（基准数的位置先被第一个小于基准数的占用，后面全部交换完成，留下的坑位就是基准数的位置）

 1 public static void sort(int[] arr){
 2         sort(arr,0,arr.length-1);
 3 }
 4 
 5 public static void sort(int[] arr, int left, int right) {
 6         if (left >= right){
 7             return;
 8         }
 9         int p = partition(arr,left,right);
10         sort(arr,left,p-1);
11         sort(arr,p+1,right);
12  }
13 
14 public static int partition(int[] arr, int left, int right) {
15         int base = arr[left];
16         int i = left;
17         int j = right;
18         //一直挖坑到左右指针重合
19         while (i<j){
20             //从右向左找到第一个小于基准值的位置
21             while (arr[j]>base && j>i){
22                 j--;
23             }
24             //找到后填左指针的坑，留下坑位，左指针前进一位(填哪侧的坑，哪测前进，否则就重复填了)
25             if (i<j){
26                 arr[i] = arr[j];
27                 i++;
28             }
29             //从左向右找到第一个大于基准值的位置
30             while (arr[i]j){
31                 i++;
32             }
33             //找到后填右指针的坑，留下坑位，右指针前进一位
34             if(i<j){
35                 arr[j]=arr[i];
36                 j--;
37             }
38         }
39         //循环结束后，i=j，就是基准值的坑位
40         arr[i] = base;
41         return i;
42  }