龙采哈尔滨建站公司,怎样做app,做网站配送地址怎么变换,珠海市网站建设的公司排序算法-基数排序法#xff08;RadixSort#xff09;
1、说明
基数排序法与我们之前讨论的排序法不太一样#xff0c;并不需要进行元素之间的比较操作#xff0c;而是属于一种分配模式排序方式。
基数排序法比较的方向可分为最高位优先#xff08;Most Significant Di…排序算法-基数排序法RadixSort
1、说明
基数排序法与我们之前讨论的排序法不太一样并不需要进行元素之间的比较操作而是属于一种分配模式排序方式。
基数排序法比较的方向可分为最高位优先Most Significant Digit FirstMSD和最低位优先Least Significant Digit FirstLSD两种。MSD是从最左边的位数开始比较的而LSD则是从最右边的位数开始比较的。 2、算法分析
在所有情况下时间复杂度均为k是原始数据的最大值。基数排序法是稳定排序法。基数排序法要使用很大的额外空间来存放列表数据其空间复杂度为n是原始数据的个数p是数据字符数。若n很大p固定或很小则此排序法的效率很高。 3、C代码
#includeiostream
#includeiomanip
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;
}
输出结果
