数据结构与算法专栏 —— C++实现
写在前面：
今天我们继续来整理与 O(n+k) 有关的三个排序算法，即计数排序、桶排序和基数排序。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n2) | O(n+k) | 稳定 |
| 基数排序 | O(n×k) | O(n×k) | O(n×k) | O(n+k) | 稳定 |
计数排序是去统计每个值在数组中的数量，然后依次放在它们应该在的位置，所以这个算法不适合数组中的值过大，因为这是用空间来换时间。并且，计数排序也不适合按照字符串进行排序。算法步骤如下：
- 找到数组中最大的值，进行初始化操作。
- 统计数组中个数值的个数。
- 对所有的计数进行累加（等于求前缀和）。
- 将每个元素放到新的数组中去。
直接上图：
我们对数组先进行遍历，统计每个数值的个数。
统计完数量后，计算前缀和：
然后对每个元素的位置进行推断，可能会有小伙伴比较疑惑为什么要弄的这么麻烦，直接从前往后根据下标输出不就好了吗。这是因为每个元素都是一个个体，如果遇到相同元素为了保证稳定性，即排序后相同元素前后次序和原数组中的前后顺序要保持一致。
为了避免数据混乱即保持稳定性，我们从后往前进行遍历。每次都将元素对应的 nums 值减 1 ，然后从后往前赋值给 dis 数组（用来保存最终元素位置）。现在可能听起来会有点晕，我们直接看图。
至此，dis 数组更新完毕，我帮你将 dis 数组和 arr 数组放在一起。
现在是不是更清楚了，我们只用根据得到的 dis 数组将原数组中的元素放在 dis 数组中要求放的位置即可。
#include桶排序using namespace std; //计数排序 void countSort(int arr[], int size, int maxnum) { int m = maxnum + 1; vector count(m); //计算数据的个数 vector nums(m); //计算每个位置与前面的数据个数总和 vector dis(size); //记录数据位置信息 vector newarr(size); //储存排序后的数组 //计算数据个数 for (int i = 0; i < size; i++) count[arr[i]]++; //计算数据总和 nums[0] = count[0]; for (int i = 1; i < m; i++) nums[i] += nums[i - 1] + count[i]; //推断数据位置信息 for (int i = size - 1; i >= 0; i--) { //从后往前查找，避免数据顺序混乱 int x = arr[i]; nums[x]--; dis[i] = nums[x]; } //数据排序 for (int i = 0; i < size; i++) newarr[dis[i]] = arr[i]; //输出数组 for (int i = 0; i < size; i++) cout << newarr[i] << " "; } int main() { int arr[10] = { 2, 3, 1, 8, 5, 10, 4, 3, 9, 6 }; int size = 10, maxnum = 10; countSort(arr, size, maxnum); return 0; }
桶排序就是创建若干个桶，每个桶代表一个区间，然后将数组中的元素放入对应的桶中。算法步骤如下：
- 具体要建立多少个桶根据元素的最大和最小值而定，我们这里采用如下公式确定。
区间大小 = （最大值 - 最小值）/（通的数量 - 1） - 遍历原始数组，根据区间将元素放入对应的桶中。
- 将每个桶内的元素进行排序。
- 遍历所有的桶，将所有元素串起来输出。
不过因为桶排序不是很重要，计数排序和基数排序才是重点。我们下面实现的是最简单的方法，即直接根据元素最大值创建相应的桶，并且遍历进行计数，最后输出。由于简单的实现方法比较易懂，我就直接上代码啦~
#include基数排序using namespace std; //计数排序 void bucketSort(int arr[], int size, int maxnum) { vector newarr(size); vector bucket(maxnum + 1, 0); //进行计数 for (int i = 0; i < size; i++) bucket[arr[i]]++; //进行输出 for (int i = 0; i < maxnum; i++) { while (bucket[i]) { cout << i << " "; bucket[i]--; } } } int main() { int arr[10] = { 2, 3, 1, 8, 5, 10, 4, 3, 9, 6 }; int size = 10, maxnum = 10; bucketSort(arr, size, maxnum); return 0; }
基数排序是一种多关键字的排序算法，算法步骤如下：
- 找到数组中最大的元素，并获得其位数。
- 从个位开始到最大元素最高位，对每个数根据每个位进行排序。
- 每次排序完之后，都从对每个位排好序的数组中取出来连成一串，最终得到有序的序列。
直接上图：
假设初始数组为 { 10 , 278 , 109 , 63 , 930 , 589 , 184 , 505 , 269 , 8 , 83 } 。
第一步：获得数组元素中最大的元素即 930 ，计算其位数为 3 。
第二步：对每个元素的个数进行排序，下面遇到相同位置的元素我们用链表串起来，并且用尾插法进行插入。
第三步：个位数排序已完成，将数组中元素依次输出，连成一串。
第四步：对十位数进行排序。
第五步：十位数排序已完成，将数组中元素依次输出，连成一串。
第六步：对百位数进行排序。
第七步：百位数排序已完成，将数组中元素依次输出，连成一串。
至此，排序位数已经是最大数字的最大位数即 3 ，故排序结束，输出数组。
下面代码部分我们加入了对负数进行排序的操作，如果数组中存在负数，则将数组中所有元素先加上数组中最小负数的绝对值再进行基数排序（因为基数排序用的数组下标都必须大于零），最后输出的时候再减去最小负数的绝对值。
另外，我们对每一趟排序都进行了输出方便大家观察结果。
#includeusing namespace std; struct Node { int val = INT_MAX; Node *next = NULL; }; int res, minx; void Sort(int a[], Node *arr[]) { int cnt = 0; //将下标数组中的元素取出排成一列 for (int i = 0; i < 10; i++) { Node *temp = arr[i]->next; while (temp != NULL) { a[cnt++] = temp->val; temp = temp->next; } } //将下标数组初始化 for (int i = 0; i < 10; i++) { arr[i]->next = NULL; } //如果原数组中存在负数，则还原数组 if (minx < 0) { cout << a[0] - res; for (int i = 1; i < cnt; i++) cout << " " << a[i] - res; } else { cout << a[0]; for (int i = 1; i < cnt; i++) cout << " " << a[i]; } cout << endl; } //桶排序 void BarrelSort(int a[], Node *arr[], int size, int flag) { int x = 1; //判断是对哪个位置进行排序 while (flag != 1) { x *= 10; flag--; } //进行对应位置的排序 for (int i = 0; i < size; i++) { Node *node = new Node; node->val = a[i]; Node *temp; temp = arr[a[i] / x % 10]; while (temp->next != NULL) { temp = temp->next; } node->next = temp->next; temp->next = node; } //输出排好序的桶 for (int i = 0; i < 10; i++) { cout << i << ":"; if (arr[i]->next == NULL) { cout << "NULL" << endl; continue; } Node *temp = arr[i]->next; while (temp != NULL) { cout << "->" << temp->val; temp = temp->next; } cout << "->^" << endl; } Sort(a, arr); } //基数排序 void cardinalSort(int a[], int size, int k) { Node *arr[10]; //根据下标大小存放节点 //初始化数组 for (int i = 0; i < 10; i++) { Node *node = new Node; arr[i] = node; } //对数字的每一位进行桶排序 for (int i = 1; i <= k; i++) BarrelSort(a, arr, size, i); } int main() { int t; cin >> t; //输入组数 while (t--) { int n, k = 1; cin >> n; //输出元素数量 int *a = new int[n]; minx = 0; //找到数组中最小的数 for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] < minx) minx = a[i]; } //如果数组中最小的数为负数，则所有数都加上该最小数的绝对值，为了能够后续的基数排序 if (minx < 0) { res = abs(minx); for (int i = 0; i < n; i++) a[i] = a[i] + res; } //找到数组中长度最大的数 for (int i = 0; i < n; i++) { int temp = a[i], cnt = 0; while (temp) { cnt++; temp = temp / 10; } k = max(k, cnt); } cardinalSort(a, n, k); cout << endl; } return 0; }
