20 行的快排（以尾巴为轴，与 CLRS 保持一致）

note.md

原理解析：

3 7 8 5 2 1 9 5 4
^               ^
left            right
                pivot
---------------------
3 2 8 5 7 1 9 5 4
3 2 1 5 7 8 9 5 4
3 2 1 4 7 8 9 5 5
      ^
      pivot
---------------------
3 2 1 | 7 8 9 5 5     // 分治与递归过程
    ^           ^
1 2 3 | 5 8 9 5 7
| 2 3 | | 5 9 8 7
| 2 | | | 5 7 8 9
| | | | |   ^
          5 | 8 |
          | | | |
---------------------
1 2 3 4 5 5 7 8 9

Solution.h

#include <algorithm>

class Solution {
  int partition(int arr[], int l, int r) {
    int index = l, pivot = arr[r];
    for (int i=l; i<r; ++i)
      if (arr[i] <= pivot) std::swap(arr[i], arr[index++]);
    std::swap(arr[index], arr[r]);
    return index;
  }
public:
  void quickSort(int arr[], int l, int r) {
    if (l < r) {
      int pivot = partition(arr, l, r);
      quickSort(arr, l, pivot-1);
      quickSort(arr, pivot+1, r);
    }
  }
};