济南咨询行业网站开发,WordPress数据库大,ui设计官网,旅游网站建设价格核心思想是按位排序#xff08;低位到高位#xff09;。适用于定长的整数或字符串#xff0c;如例如#xff1a;手机号、身份证号排序。按数据的每一位从低位到高位#xff08;或相反#xff09;依次排序#xff0c;每次排序使用稳定的算法#xff08;如计数排序#…核心思想是按位排序低位到高位。适用于定长的整数或字符串如例如手机号、身份证号排序。按数据的每一位从低位到高位或相反依次排序每次排序使用稳定的算法如计数排序。
#include stdlib.h
// 获取数组中最大值用于确定位数
int getMax(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}return max;
}// 使用计数排序对指定位数进行排序exp1,10,100...
void countSort(int arr[], int n, int exp) {int* output (int*)malloc(n * sizeof(int)); // 输出数组int count[10] {0}; // 十进制计数数组// 统计当前位数字出现次数for (int i 0; i n; i) {count[(arr[i] / exp) % 10];}// 计算累计位置稳定排序关键for (int i 1; i 10; i) {count[i] count[i - 1];}// 反向填充保证稳定性相同数字保持原顺序for (int i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}// 将排序结果复制回原数组for (int i 0; i n; i) {arr[i] output[i];}free(output);
}// 基数排序主函数LSD最低位优先
void radixSort(int arr[], int n) {int max getMax(arr, n);// 按每一位进行计数排序for (int exp 1; max / exp 0; exp * 10) {countSort(arr, n, exp);}
}#include stdio.h
// 打印数组
void printArray(int arr[], int n) {for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {170, 45, 75, 90, 802, 24, 2, 66}; // 测试数据int n sizeof(arr) / sizeof(arr[0]);printf(排序前: );printArray(arr, n);radixSort(arr, n);printf(排序后: );printArray(arr, n);return 0;
}
优化建议
1.基数选择优化使用更大的基数如256减少迭代次数提升缓存利用率
2.内存预分配预分配输出数组空间减少多次内存分配开销
3负数处理分离符号位单独处理支持负数排序
扩展优化示例支持负数
void radixSortWithNegative(int arr[], int n) {// 分离正负数int* positive malloc(n * sizeof(int));int* negative malloc(n * sizeof(int));int pos_count 0, neg_count 0;for (int i 0; i n; i) {if (arr[i] 0) {positive[pos_count] arr[i];} else {negative[neg_count] -arr[i]; // 取绝对值处理}}// 分别排序正负数radixSort(positive, pos_count);radixSort(negative, neg_count);// 合并结果负数逆序int index 0;for (int i neg_count - 1; i 0; i--) {arr[index] -negative[i];}for (int i 0; i pos_count; i) {arr[index] positive[i];}free(positive);free(negative);
}
