河北省建设厅正规网站,怎样快速建设网站模板,联想官方服务网站,亚马逊入驻费用及条件统计每个元素出现的次数#xff0c;直接计算元素在有序序列中的位置#xff0c;要求数据是整数且范围有限。适用于数据为小范围整数#xff08;如年龄、成绩#xff09;#xff0c;数据重复率较高时效率更优。可用于小范围整数排序、基数排序的底层排序(作为基数排序的稳定…统计每个元素出现的次数直接计算元素在有序序列中的位置要求数据是整数且范围有限。适用于数据为小范围整数如年龄、成绩数据重复率较高时效率更优。可用于小范围整数排序、基数排序的底层排序(作为基数排序的稳定排序子过程)、统计频率分布(快速获取元素分布直方图)、海量数据预处理(配合外部排序处理大数据文件)
#include stdlib.h
#include assert.h// 计数排序核心函数稳定排序版本
void countingSort(int arr[], int n) {if (n 1) return; // 无需排序// 1. 确定数据范围int max arr[0], min arr[0];for (int i 1; i n; i) {if (arr[i] max) max arr[i];if (arr[i] min) min arr[i];}const int range max - min 1; // 实际数值范围// 2. 创建计数数组并初始化int* count (int*)calloc(range, sizeof(int));assert(count ! NULL);// 3. 统计每个元素出现次数for (int i 0; i n; i) {count[arr[i] - min]; // 偏移处理负数}// 4. 计算累计位置保证稳定性for (int i 1; i range; i) {count[i] count[i - 1];}// 5. 反向填充结果数组关键稳定性操作int* output (int*)malloc(n * sizeof(int));assert(output ! NULL);for (int i n - 1; i 0; i--) {output[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}// 6. 复制回原数组for (int i 0; i n; i) {arr[i] output[i];}// 7. 释放内存free(count);free(output);
}
#include stdio.h
// 打印数组
void printArray(int arr[], int size) {for (int i 0; i size; i) {printf(%d , arr[i]);}printf(\n);
}int main() {// 测试数据包含负数int arr[] {-5, 2, -3, 4, 1, 2, 8, 5, 3, -1};int n sizeof(arr) / sizeof(arr[0]);printf(排序前: );printArray(arr, n);countingSort(arr, n);printf(排序后: );printArray(arr, n);return 0;
}
优化建议
1.通过min值偏移处理负数支持全整数范围排序
2.通过反向遍历填充输出数组保留相同元素的原始顺序已保证稳定性
3.动态计算range值避免不必要的内存浪费
void countingSortSpaceOptimized(int arr[], int n) {// ...省略范围计算步骤...// 直接根据计数数组覆盖原数组非稳定int idx 0;for (int i 0; i range; i) {while (count[i]-- 0) {arr[idx] i min;}}
}
