基数排序
入门理解"按位处理"如何实现线性时间排序。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void radixSort(int arr[], int n) {
2 int maxVal = *max_element(arr, arr + n);
3 for (int exp = 1; maxVal / exp > 0; exp *= 10) {
4 int output[n], count[10] = {0};
5 for (int i = 0; i < n; i++)
6 count[(arr[i] / exp) % 10]++;
7 for (int i = 1; i < 10; i++)
8 count[i] += count[i - 1];
9 for (int i = n - 1; i >= 0; i--) {
10 output[count[(arr[i] / exp) % 10] - 1] = arr[i];
11 count[(arr[i] / exp) % 10]--;
12 }
13 for (int i = 0; i < n; i++)
14 arr[i] = output[i];
15 }
16}
复杂度分析
时间 O(d × n)
空间 O(n + k)
最优 O(d × n)
最坏 O(d × n)
算法讲解
基数排序从最低位开始，按每一位的值进行分桶排序。
每一轮排序保持相同位数元素的相对顺序。
经过 d 轮（d 是最大位数），数组完全有序。
时间复杂度 O(d × n)，其中 d 是位数。