# 排序
## 常考排序
### 快速排序
```c++
template
static void QuickSort(T arr[], int len) {
quickSort(arr, 0, len - 1);
}
template
static void quickSort(T arr[], int begin, int end) {
if (begin >= end) {
return;
}
auto pivot = partition(arr, begin, end);
quickSort(arr, begin, pivot - 1);
quickSort(arr, pivot + 1, end);
}
template
static int partition(T arr[], int begin, int end) {
auto base = arr[end];
auto lessInsert = begin;
for (int i = begin; i < end; ++i) {
if (arr[i] < base) {
swap(arr[lessInsert++], arr[i]);
}
}
swap(arr[lessInsert], arr[end]);
return lessInsert;
}
```
### 归并排序
```c++
template
static void MergeSort(T arr[], int len) {
auto tmp = new T[len];
mergeSort(arr, 0, len - 1, tmp);
delete[] tmp;
}
template
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
if (begin + 1 >= end) {
return;
}
auto mid = begin + (end - begin) / 2;
auto begin1 = begin;
auto end1 = mid;
auto begin2 = mid + 1;
auto end2 = end;
mergeSort(arr, begin1, end1, tmp);
mergeSort(arr, begin2, end2, tmp);
// merge two parts
auto index = begin;
while (begin1 <= end1 && begin2 <= end2) {
tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
}
while (begin1 <= end1) {
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) {
tmp[index++] = arr[begin2++];
}
for (int i = begin; i <= end; ++i) {
arr[i] = tmp[i];
}
}
```
### 堆排序
用数组表示的完美二叉树 complete binary tree
> 完美二叉树 VS 其他二叉树
[动画展示](https://www.bilibili.com/video/av18980178/)
核心代码
```c++
template
static void HeapSort(T arr[], int len) {
// right leaf of a root = 2(n + 1) since n is start from 0
auto lastRoot = len / 2 - 1;
// 先自下而上构建堆
for (int i = lastRoot; i >= 0; --i) {
makeHeap(arr, i, len);
}
for (int j = len - 1; j >= 0; --j) {
// 最大值放到后面
swap(arr[0], arr[j]);
// 底部都还是有序的，只动了根节点，自上而下更新堆
makeHeap(arr, 0, --len);
}
}
template
static void makeHeap(T arr[], int root, int len) {
auto left = root * 2 + 1;
auto right = (root + 1) * 2;
auto largest = root;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest == root) {
return;
}
swap(arr[largest], arr[root]);
makeHeap(arr, largest, len);
}
```
## 参考
[十大经典排序](https://www.cnblogs.com/onepixel/p/7674659.html)
[二叉堆](https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/er-cha-dui-xiang-jie-shi-xian-you-xian-ji-dui-lie)
## 练习
- [ ] 手写快排、归并、堆排序