数据结构与算法篇-基数排序
时间：2021-08-19 15:30:18
手机看文章
扫描二维码
随时随地手机看文章
[导读]01—基数排序算法思想输入n个d位数，现在要对n个数进行排序，就需要设计一个排序算法法。基数排序算法思想：先对最低有效位采用稳定排序算法进行排序，然后从次最低有效位到最高有效位依次采用稳定排序算法进行排序，处理完最高有效位后则是最终排序后的结果。这里说明一下什么是稳定排序算法和不...
01—基数排序算法思想
输入n个d位数，现在要对n个数进行排序，就需要设计一个排序算法法。基数排序算法思想：先对最低有效位采用稳定排序算法进行排序，然后从次最低有效位到最高有效位依次采用稳定排序算法进行排序，处理完最高有效位后则是最终排序后的结果。这里说明一下什么是稳定排序算法和不稳定排序算法：大小相同的数字A和B分别在原始序列中的索引是x和y，且x>y。经过排序后A和B分别所在输出序列的索引是x1和y1，如果x1>y1，那么这个排序算法是稳定的，如果x1
02—基数排序算法实现基数排序算法的实现最重要的是各个有效位使用的排序算法，已知计数排序算法的时间复杂度是O(n k)，如果基数排序采用计数排序对n个d位的数字进行排序，那么时间复杂度是O(d(n k))，现在我们用计数排序算法实现基数排序算法。
//求取最大值
static int get_max(int *arr, int length){
int i = 0;
int max = 0;
max = arr[0];
for(i = 1; i < length; i ){
if(arr[i] > max){
max = arr[i];
}
}
return max;
}
//计数排序
void count_sort(int *arr, int length, int exp){
if(arr == NULL || length <= 0 || exp <= 0){
return;
}
int bucket[10] = {0};
int *output = (int *)malloc(sizeof(int) * length);
if(output == NULL){
return;
}
memset(output, 0, sizeof(int) * length);
int i = 0;
for(i = 0; i < length; i ){
bucket[(arr[i] / exp) % 10] ;
}
for(i = 1; i < length; i ){
bucket[i] = bucket[i - 1];
}
for(i = length - 1; i >= 0; i--){
output[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
bucket[(arr[i] / exp) % 10]--;
}
for(i = 0; i < length; i ){
arr[i] = output[i];
}
free(output);
}
//基数排序
void radix_sort(int *arr, int length){
if(arr == NULL || length <= 0){
return;
}
int exp = 0;
int max = get_max(arr, length);
for(exp = 1; max / exp; exp *= 10){
count_sort(arr, length, exp);
}
}最后写一个小程序验证算法的正确性。
#include
#include "radix_sort.h"
int main() {
int arr[10] = {873, 12, 89, 256, 978, 67, 56434, 654, 24345, 9};
radix_sort(arr, 10);
int i = 0;
printf("基数排序结果\n");
for(i = 0; i < 10; i ){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}编译运行输出如下：
基数排序结果
9 12 67 89 256 654 873 978 24345 56434输出完全正确。
版权申明：内容来源网络，版权归原创者所有。除非无法确认，都会标明作者及出处，如有侵权烦请告知，我们会立即删除并致歉。谢谢!
下载文档
