排序算法
2024年2月2日大约 4 分钟约 1165 字
1. 内部排序
算法 | 平均时间 | 最坏情况 | 辅助存储 | 稳定性 |
---|---|---|---|---|
冒泡顺序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
插入排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
希尔排序 | $O(n\log{n})$ | $O(n\log^2{n})$ | $O(1)$ | 不稳定 |
选择排序 | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
归并排序 | $O(n\log{n})$ | $O(n\log{n})$ | $O(n)$ | 稳定 |
快速排序 | $O(n\log{n})$ | $O(n^2)$ | $O(\log{n})$ | 不稳定 |
堆排序 | $O(n\log{n})$ | $O(n\log{n})$ | $O(1)$ | 不稳定 |
桶排序 | $O(n+k)$ | $O(n^2)$ | $O(n+k)$ | 稳定 |
基数排序 | $O(n \times k)$ | $O(n \times k)$ | $O(n+k)$ | 稳定 |
1.1 冒泡排序
Bubble Sort
#include <vector>
using namespace std;
void bubbleSort(vector<int>& arr) {
for (long i = 0; i < arr.size(); i++) {
bool flag = true;
for (long j = 0; j < arr.size() - i - 1; j++)
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
flag = false;
}
if (flag == true) return;
}
}
1.2 插入排序
Insert Sort
#include <vector>
using namespace std;
void insertSort(vector<int>& arr) {
// 插入排序将序列分为已排序的前缀和未排序的后缀
// 插入排序每次从后缀中选取一个元素,然后将其插入已有序的前缀
for (long i = 1; i < arr.size(); i++) {
// arr[i] denotes the current target to be inserted into the sorted
// prefix, and j moves in the sorted prefix from the maximum to minimum
int target = arr[i];
long j = i - 1;
while (j >= 0)
// 如果待插入对象target位于arr[j]左侧,应继续移动
if (target < arr[j]) {
arr[j + 1] = arr[j];
--j;
} else // 已找到待插入对象应该插入的位置
break;
arr[j + 1] = target;
}
}
1.3 希尔排序
1.4 选择排序
Select Sort
#include <vector>
using namespace std;
void selectSort(vector<int>& arr) {
// 选择排序将序列分为无序的前缀和有序的后缀,且前缀中的所有元素都比后缀中的元素要小
// 每次选择前缀中的最大值,然后插入后缀的首元素之前即可
for (long i = arr.size() - 1; i >= 0; --i) {
int max = arr[i]; // 先假定无序前缀的最大值为其最后一个元素
long rank = i; // 最大值对应的秩
for (long j = 0; j < i; j++) // 在无序前缀中寻找真正的最大值
if (arr[j] >= max) {
max = arr[j];
rank = j;
}
swap(arr[rank], arr[i]); // 更新
}
}
1.5 归并排序
Merge Sort
#include <vector>
using namespace std;
void merge(vector<int>&, long, long, long); // 声明
void mergeSort(vector<int>& arr, long lo, long hi) { // 左闭右开[lo, hi)
if (hi - lo < 2) return; // 单元素区间自然有序
long mi = (lo + hi) / 2;
mergeSort(arr, lo, mi); // 排序左区间[lo, mi)
mergeSort(arr, mi, hi); // 排序右区间[mi, hi)
merge(arr, lo, mi, hi); // 归并
}
void merge(vector<int>& arr, long lo, long mi, long hi) {
long frontLen = mi - lo; // 前(左)子向量的长度
auto frontCopy = new int[frontLen];
for (long i = 0; i < frontLen; i++) // 复制前(左)子向量
frontCopy[i] = arr[lo + i];
long i = lo, l = 0, r = mi; // index of total, left, right vector
while (i < hi) {
if (r >= hi || (l < frontLen && frontCopy[l] <= arr[r]))
arr[i++] = frontCopy[l++];
if (l >= frontLen || (r < hi && arr[r] < frontCopy[l]))
arr[i++] = arr[r++];
}
delete[] frontCopy;
}
上述merge
函数中的while (i < hi) {}
循环体稍显晦涩,可等效地拆解为如下三个部分:
while (l < frontLen && r < hi) {
if (frontCopy[l] <= arr[r])
arr[i++] = frontCopy[l++];
else {
count += r - mi + 1;
arr[i++] = arr[r++];
}
}
while (l < frontLen) arr[i++] = frontCopy[l++]; // 前子向量未处理完时
while (r < hi) arr[i++] = arr[r++]; // 后子向量未处理完时
1.6 快速排序
Quick Sort
#include <vector>
using namespace std;
long partition(vector<int>&, long, long); // 声明
void quickSort(vector<int>& arr, long lo, long hi) {
if (hi - lo < 2) return; // 单元素区间自然有序
// 在[lo, hi)内构造支(轴)点,将原向量分割为两部分
// 轴点的作用是,其左侧的元素均不大于轴点元素,其右侧的值均不小于轴点值
long mi = partition(arr, lo, hi);
quickSort(arr, lo, mi); // 对前缀递归排序
quickSort(arr, mi + 1, hi); // 对后缀递归排序
}
long partition(vector<int>& arr, long lo, long hi) { // 轴点构造算法
// 任选一个元素与首元素交换
long rank = lo + rand() % (hi - lo);
swap(arr[lo], arr[rank]);
int pivot = arr[lo]; // 以首元素为候选支(轴)点——经以上交换,等效于随机选取
while (lo < hi - 1) {
while (lo < hi - 1 && pivot <= arr[hi - 1]) --hi; // 向左扩展右端子向量
arr[lo] = arr[hi - 1];
while (lo < hi - 1 && arr[lo] <= pivot) ++lo; // 向右扩展左端子向量
arr[hi - 1] = arr[lo]; // 大于pivot者归入右侧子序列
} // assert: lo == hi - 1
arr[lo] = pivot; // 将备份的轴点记录置于前、后子向量之间
return lo; // 返回轴点的秩,即母算法中需要的切分点的位置
}
1.7 堆排序
1.8 桶排序
1.9 基数排序
2. 外部排序
To be continued.