1、两种不同的排序方法

图解：https://blog.csdn.net/csdnsevenn/article/details/81844085

1.1、挖坑法

总结：就是基准所在的位置被挖了一个坑，然后不断的填坑、挖坑

1.2、指针交换法

总结：就是比较不挖坑，而是交换。

2、时间复杂度

时间复杂度只和选的基准有关。如果基准选的不好，比如想正序排序，但是数组是 9,8,7,6,5这种倒序排列的，此时选择第一位，即9为基准，就会导致整个排序算法的复杂度退化成n平方。

3、代码实现

  1.     // 解法3： 挖坑法
  2.     // arr[l++] = arr[r];说明左边的坑被填上了:
  3.     public void quick2(int[] arr, int left, int right) {
  4.         //先判断left<right，为true才能遍历
  5.         if (left < right) {
  6.             int pivot = arr[left], l = left, r = right;
  7.             while (l < r) {
  8.                 while (arr[r] >= pivot && l < r) { // arr[r]>= pivot
  9.                     // ,这里加=，是为了不移动和pivot相等的元素，节约减少系统操作
  10.                     r--;
  11.                 }
  12.                 if (l == r) {
  13.                     //如果l=r,就遍历到头了，退出
  14.                     break;
  15.                 }
  16.                 //如果右边停下了，挖出来填左边坑，然后让左边去走
  17.                 arr[l++] = arr[r];
  18.                 while (arr[l] <= pivot && l < r) {
  19.                     l++;
  20.                 }
  21.                 if (l == r) {
  22.                     //如果l=r,就遍历到头了，退出
  23.                     break;
  24.                 }
  25.                 // 如果左边停下了，挖出来填右边坑，然后让右边去走
  26.                 arr[r--] = arr[l];
  27.             }
  28.             //不管是左边遍历右边，还是右边遍历左边，最后退出后一定有 l==r;
  29.             //因为右边遍历左边的时候，左边一定有个坑了(此时坑的索引是l)，如果这个循环一直r--，直到l=r的时候退出，那么最后r一定也在坑里。
  30.             //同理左边遍历右边的时候，右边一定有个坑了(此时坑的索引是r)，如果这个循环一直l++，直到l=r的时候退出，那么最后l一定也在坑里。
  31.             //此时直接让pivot去填上这个坑就行了。
  32.             arr[l] = pivot;
  33.             quick2(arr, left, l - 1);
  34.             quick2(arr, r + 1, right);
  35.         }
  36.     }
  1.     // 解法1：
  2.     public void quickSort(int[] arr, int left, int right) {
  3.         int l = left, r = right, pivot = arr[(left + right) / 2];
  4.         int temp = 0;
  5.         //while循环使 比pivo t值小的放左边
  6.         //比pivot大的放右边
  7.         while (l < r) {
  8.             //在pivot的左边一直找，找到 >= pivot的值，才退出
  9.             while (arr[l] < pivot) l++;
  10.             //在pivot的右边一直找，找到 <= pivot的值，才退出
  11.             while (arr[r] > pivot) r--;
  12.             //如果l >= r说明pivot的左边全都小于pivot，右边全大于
  13.             if (l == r) break;
  14.             //交换
  15.             temp = arr[l];
  16.             arr[l] = arr[r];
  17.             arr[r] = temp;
  18.             //如果交换完后，arr[l] == pivot，r--，前移
  19.             if (arr[l] == pivot) r--;
  20.             if (arr[r] == pivot) l++;
  21.         }
  22.         // 如果 l==r，必须l++,r--,否则会出现栈溢出
  23.         if (l == r) {
  24.             l++;
  25.             r--;
  26.         }
  27.         //向左递归
  28.         if (left < r) quickSort(arr, left, r);
  29.         if (right > l) quickSort(arr, l, right);
  30.     }

赫本一生改嫁三次，都没有选择纪梵希，而纪梵希一生未娶，大概真爱的真谛不是占有，而是，我喜欢你，你随意即可
赫本一生改嫁三次，都没有选择纪梵希，而纪梵希一生未娶，大概真爱的真谛不是占有，而是，我喜欢你，你随意即可