实现快排的思路

双指针实现，选定一个基准值，分别对基准值左右两个子序列进行递归操作，使其变得有序（即比基准值大的放右边，比基准值小的放左边），重要的是基准值，算法快慢取决于基准值的位置。
普通快速排序.jpg

如何获取基准值

  1. 选第一个或者最后一个
    这种选取对于随机数组来说没问题，但是对于有序数组，此时为最坏情况，时间复杂度为O(n^2)
  2. 随机生成基准值
  3. 三数取中法

快速排序最好情况的时间复杂度为O(nlogn)

代码实现

  1. // 快速排序
  2. public static void subSort(int[] arr, int start, int end) {
  3.     if (start > end) {
  4.         return;    
  5.     }
  7.     if (start < end) {
  8.         int low = start;
  9.         int high = end;
  10.         int base = arr[start];  // 基准值，取左边第一个
  12.         while (low < high) {
  13.             while (low < high && arr[high] >= base) {
  14.                 high--;
  15.             }
  16.             arr[low] = arr[high];   // 当arr[high]小于基准值，就要赋值给arr[left]
  17.             while (low < high && arr[low] <= base) {
  18.                 low++;
  19.             }
  20.             arr[high] = arr[low];   // 当arr[low]大于基准值，就要赋值给arr[high]
  21.         }
  22.         arr[low] = base;    // 此时low = high，用基准值来填这个坑
  23.         subSort(arr, start, low - 1);
  24.         subSort(arr, low + 1, end);
  25.     }
  26. }