//将一个数组按照第一个元素进行分组,返回分组的位置
template <typename T> int groupArray(T arr[], int n) {

  T mid = arr[0];
  //比mid小于等于的元素和比mid大于等于的元素的分几点arr[1...j]<=mid,arr[j+1...i-1]>mid
  int j = 0;
  //遍历数组的索引
  int i = 1;

  for (; i < n; i++) {
    //如果当前元素比mid小,交换arr[i]和arr[j+1].将j递增.否则直接i即可
    if (arr[i] <= mid) {
      using std::swap;
      swap(arr[i], arr[j + 1]);
      j++;
    }
  }

  //最终将第一个元素和arrr[j]交换
  using std::swap;
  swap(arr[0], arr[j]);

  return j;
}

//快速排序v1
template <typename T> void quickSort(T arr[], int n) {
  //获得第一次分组的位置
  int mid = groupArray(arr, n);
  //如果此时n<=2就不在分组
  if (n <= 2)
    return;
  //将左右两边继续快速排序
  if (mid > 1)
    quickSort(arr, mid);
  if (n - mid > 2)
    quickSort(arr + mid + 1, n - mid - 1);
}

同样是1000000的随机数组,为啥差别折磨大