排序算法-基数排序法(RadixSort)
1、说明
基数排序法与我们之前讨论的排序法不太一样,并不需要进行元素之间的比较操作,而是属于一种分配模式排序方式。
基数排序法比较的方向可分为最高位优先(Most Significant Digit First,MSD)和最低位优先(Least Significant Digit First,LSD)两种。MSD是从最左边的位数开始比较的,而LSD则是从最右边的位数开始比较的。
2、算法分析
- 在所有情况下,时间复杂度均为,k是原始数据的最大值。
- 基数排序法是稳定排序法。
- 基数排序法要使用很大的额外空间来存放列表数据,其空间复杂度为,n是原始数据的个数,p是数据字符数。
- 若n很大,p固定或很小,则此排序法的效率很高。
3、C++代码
#include<iostream>
#include<iomanip>
using namespace std;void PrintData(int data[], int size) {for (int i = 0; i < size; i++) {cout << data[i] << " ";}cout << endl;
}void SetData(int data[], int size) {srand(time(nullptr));for (int i = 0; i < size; i++) {data[i] = rand() % 999 + 1;}
}void Radix(int data[], int size) {for (int n = 1; n <= 100; n *= 10) {int temp[10][100] = { 0 };for (int i = 0; i < size; i++) {int m = (data[i] / n) % 10;temp[m][i] = data[i];}int k = 0;for (int i = 0; i < 10; i++) {for (int j = 0; j < size; j++) {if (temp[i][j] != 0) {data[k] = temp[i][j];k++;}}}cout << "经过" << setw(3) << n << "位排序后:";PrintData(data, size);}
}int main() {int size = 20;int* data = new int[size];SetData(data, size);cout << "原始数据:";PrintData(data, size);cout << "---------------------------------" << endl;Radix(data, size);cout << "---------------------------------" << endl;cout << "最终数据:";PrintData(data, size);return 0;
}
输出结果