基数排序c++实现代码
时间: 2023-12-07 10:38:09 浏览: 34
以下是基数排序的C++实现代码:
```
#include <iostream>
#include <cstring>
using namespace std;
// 获取num从右往左第d位的数字
int GetNum(int num, int d) {
int pow = 1;
for (int i = 0; i < d - 1; i++) {
pow *= 10;
}
return (num / pow) % 10;
}
// 基数排序
void RadixSort(int* input, int length) {
int maxNum = input[0];
for (int i = 1; i < length; i++) {
if (input[i] > maxNum) {
maxNum = input[i];
}
}
int* bucket = new int[length];
int* count = new int[10];
for (int d = 1; maxNum / d > 0; d *= 10) {
memset(count, 0, sizeof(int) * 10);
for (int i = 0; i < length; i++) {
int k = GetNum(input[i], d);
count[k]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = length - 1; i >= 0; i--) {
int k = GetNum(input[i], d);
bucket[count[k] - 1] = input[i];
count[k]--;
}
memcpy(input, bucket, sizeof(int) * length);
}
delete[] bucket;
delete[] count;
}
int main() {
int input[] = {0, 100, 11, 32, 123, 23, 564, 5, 56, 57, 169};
int length = sizeof(input) / sizeof(int);
RadixSort(input, length);
for (int i = 0; i < length; i++) {
cout << input[i] << " ";
}
cout << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)