请用C++写基数排序的代码
时间: 2024-05-02 07:21:51 浏览: 11
以下是基数排序的C语言代码实现:
```
#include <stdio.h>
// 获取num的第p位数字
int get_digit(int num, int p) {
int i;
for (i = 1; i < p; i++) {
num /= 10;
}
return num % 10;
}
// 基数排序
void radix_sort(int arr[], int len) {
int i, j, k;
int digit; // 当前排序的位数
int bucket[10][len]; // 桶,用于存放排序后的数字
int count[10]; // 每个桶中数字的个数
// 获取最大数的位数
int max_num = arr[0];
for (i = 1; i < len; i++) {
if (arr[i] > max_num) {
max_num = arr[i];
}
}
int max_digit = 0;
while (max_num > 0) {
max_digit++;
max_num /= 10;
}
// 对每个位数进行排序
for (digit = 1; digit <= max_digit; digit++) {
// 初始化桶和计数器
for (i = 0; i < 10; i++) {
count[i] = 0;
}
// 将数字放入桶中
for (i = 0; i < len; i++) {
int d = get_digit(arr[i], digit);
bucket[d][count[d]] = arr[i];
count[d]++;
}
// 将桶中的数字放回原数组
k = 0;
for (i = 0; i < 10; i++) {
for (j = 0; j < count[i]; j++) {
arr[k] = bucket[i][j];
k++;
}
}
}
}
int main() {
int arr[] = { 53, 3, 542, 748, 14, 214, 154, 63, 616 };
int len = sizeof(arr) / sizeof(arr[0]);
radix_sort(arr, len);
printf("排序后的数组:\n");
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
基数排序的时间复杂度为O(d*(n+k)),其中d为最大数的位数,n为数组长度,k为基数(这里是10)。因此,当最大数的位数较小,且n和k较小时,基数排序的效率较高。