GitHub Viewer
# 排序
## 常考排序
### 快速排序
```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 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)
## 练习
- [ ] 手写快排、归并、堆排序