Sort¶
常见排序算法¶
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
快速排序¶
C++
void quickSort(int arr[], int low, int high) {
if (low >= high) return;
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::swap(arr[i+1], arr[high]);
int pi = i + 1;
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
归并排序¶
C++
void merge(int arr[], int l, int m, int r) {
std::vector<int> left(arr+l, arr+m+1);
std::vector<int> right(arr+m+1, arr+r+1);
int i = 0, j = 0, k = l;
while (i < left.size() && j < right.size())
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
while (i < left.size()) arr[k++] = left[i++];
while (j < right.size()) arr[k++] = right[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}