//
// Quick Sort
// Created by Win10 on 2023/4/7.
//

#ifndef C_DATA_STRUCTURE_QUICK_SORT_H
#define C_DATA_STRUCTURE_QUICK_SORT_H


#include <algorithm>

template<typename T>
//整数或浮点数皆可使用
void quick_sort(T a[], int l, int r) {
  if (l >= r) return;
  int i = l, j = r + 1;
  int x = a[l];
  while (true) {
    //从左向右找比x大的值
    while (a[++i] < x)
      if (i == r) break;
    //从右向左找比x小的值
    while (a[--j] > x)
      if (j == l) break;
    if (i >= j) break;
    //交换i,j对应的值
    std::swap(a[i], a[j]);
  }
  //中枢值与j对应值交换
  std::swap(a[l], a[j]);
  quick_sort(a, l, j - 1);
  quick_sort(a, j + 1, r);
}

#endif //C_DATA_STRUCTURE_QUICK_SORT_H