写在前面
总结算法导论中的线性排序算法, C++实现.
计数排序
通过给定范围计数完成排序, 需要额外空间, 但是时间复杂度能到线性, 是稳定的排序算法.
void ConutingSort(vector<int>& arr) {
int n = arr.size(), k = *max_element(arr.begin(), arr.end());
vector<int> C(k + 1), B(n);
for (int num : arr) C[num]++;
// 前缀和
for (int i{}; i < k; ++i) C[i + 1] += C[i];
for (int num : arr) B[--C[num]] = num;
arr = B;
}
基数排序
从个位开始, 每次操作数字的一个位, 不断调整顺序, 得到排序好的数组.
void RadixSort(vector<int>& arr) {
int n = arr.size(), d{};
int mx = *max_element(arr.begin(), arr.end());
while (mx) mx /= 10, ++d;
vector<int> tmp(n), count(10);
int i, j, k, radix = 1;
for (i = 1; i <= d; i++) {
fill(count.begin(), count.end(), 0); // 每次分配前清空计数器
// 统计每个桶中的记录数(通过`余数`来区分放入哪个桶, 共有10个桶)
for (int num : arr) count[(num / radix) % 10]++;
// 将tmp中的位置依次分配给每个桶(前缀和)
for (j = 1; j < 10; j++) count[j] += count[j - 1];
// 将所有桶中记录依次收集到tmp中
for (j = n - 1; j >= 0; j--)
tmp[--count[(arr[j] / radix) % 10]] = arr[j];
// 将临时数组的内容复制到arr中
arr = tmp;
// 进位, 开始操作十位, 百位..
radix = radix * 10;
}
}
桶排序
有条件, 最好让待排序的数字满足均匀分布, 这里以在0~100之间的数字为例, 通过对十位的不同分成十个桶, 然后对桶中元素插入排序之后合并.
void InsertionSort(vector<int>& A) {
int n = A.size();
// 待插入的元素
for (int i = 1; i < n; ++i) {
int tmp = A[i], j = i - 1;
for (; j >= 0 && A[j] > tmp; --j) A[j + 1] = A[j];
A[j + 1] = tmp;
}
}
void BucketSort(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> B(10);
for (int num : arr) B[num / 10].emplace_back(num);
int i{};
for (vector<int>& A : B) {
InsertionSort(A);
for (int a : A) arr[i++] = a;
}
}