前言
本文介绍一种排序算法——基数排序，是经典排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。
一、基数排序简介
基数排序不需要进行元素之间的比较操作，而是一种分配模式排序方式。基数排序法按比较的方向可分为最高位优先（Most Significant Digit First，MSD）和最低位优先（Least Significant Digit First，FSD）两种。MSD是从最左边的位数开始比较，而LSD则是从最右边的位数开始比较。一般常选择LSD。
基数排序法的实现思路：
- 计算数列最大值，并确认其位数。
- 从最高位或最低位开始，结合临时创建的二维数组，进行放置操作；合并数据完成当前位数级的排序。
- 位数递减或递增，按上述操作执行，直到所有位数遍历过一遍，此时完成排序。
二、算法特点
1）所有情况下的时间复杂度为O(kn)。但是这个常数k蛮大的，并不能因为复杂度是n就觉得它一定快。
2）稳定，合并过程不改变原序列过程。
3）空间复杂度是O(n*p)，需要用很大的额外空间做辅助，p是最大位数，比如1000的位数是4。
三、代码实现
代码实现逻辑：
- 确认最大值。
- 计算最大位数。
- 从最左或最右位数，按位数放置在二维数组中，并重新组建新数列。
- 所有位数遍历一遍，此时数列完成排序。
// 基数排序 void RadixSort(vector<int> &data) { // 确认最大值 int size = int(data.size()); int max = data[0]; for (int i = 1; i < size; ++i) { if (data[i] > max) max = data[i]; } // 计算位数 int n = 1; int temp = max / 10; while (temp != 0) { temp /= 10; n++; } // 主过程 int b = 1; for (int k = 1; k <= n; ++k) { // 初始化二维数组 vector<vector<int>> tmp(10, vector<int>(size, -1)); // 根据b位数级数字，放置在对应位置 for (int i = 0; i < size; ++i) { int m = (data[i] / b) % 10; tmp[m][i] = data[i]; } // 依次放回data int p = 0; for (int i = 0; i < 10; ++i) { for (int j = 0; j < size; ++j) { if (tmp[i][j] != -1) { data[p] = tmp[i][j]; p++; } } } b *= 10; } }
四、C++示例
#include <iostream> #include <iomanip> #include <vector> #include <string> #include <opencv2/opencv.hpp> #include <fstream> #include <sstream> #include <armadillo> #include <math.h> #include <assert.h> using namespace std; using namespace cv; #define M_PI 3.1415 // 展示当前顺序 void Show(vector<int> data) { size_t size = data.size(); for (size_t i = 0; i < size; ++i) cout << setw(6) << data[i]; cout << endl; } // 基数排序 void RadixSort(vector<int> &data) { cout << "基数排序：\n原始数据：\n"; Show(data); // 确认最大值 int size = int(data.size()); int max = data[0]; for (int i = 1; i < size; ++i) { if (data[i] > max) max = data[i]; } // 计算位数 int n = 1; int temp = max / 10; while (temp != 0) { temp /= 10; n++; } // 主过程 int b = 1; for (int k = 1; k <= n; ++k) { // 初始化二维数组 vector<vector<int>> tmp(10, vector<int>(size, -1)); // 根据b位数级数字，放置在对应位置 for (int i = 0; i < size; ++i) { int m = (data[i] / b) % 10; tmp[m][i] = data[i]; } // 依次放回data int p = 0; for (int i = 0; i < 10; ++i) { for (int j = 0; j < size; ++j) { if (tmp[i][j] != -1) { data[p] = tmp[i][j]; p++; } } } b *= 10; cout << "第" << k << "次排序结果：\n"; Show(data); } cout << "排序后结果：\n"; Show(data); } // 主函数 int main() { vector<int> data = { 9,11,567,0,26,4,2,12,18,6,9,5378,102,8 }; // 基数排序 RadixSort(data); system("pause"); return 0; }
效果图：
综上所述，基数排序的空间复杂度过大，而时间复杂度因为常数项的存在，也并没有优于其他算法多少，最主要的是需要先确定好基数才能排序，这有点鸡肋，因此个人不太建议使用，但是原理要清楚~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
