计数排序的应用与分析/*问题描述:某公司有几万名员工, 请完成一个时间复杂度为O(n)的算法对该公司员工的年
计数排序的应用与分析
/* 问题描述:某公司有几万名员工, 请完成一个时间复杂度为O(n)的算法对该公司员工的年龄做排序, 要 求空间复杂度为O(1) 问题分析:因为人的年龄总共也不会超过100岁，所以可以创建一个大小为100的辅助空间(数组),用于 统计各个年龄的数目,统计后在把辅助空间中对应不为0的index, 插入到对应的待排数组中 即可完成排序. 算法分析:此类排序的方式称为计数排序(couting sort), 对于任意数组我们必须知道此数组中最大 数字,才能建立辅助空间用于计数,当数组中的Maxer非常大的情况下, 需要建立极为庞大的 辅助数组,此时若数组中只有一个数,我们也要遍历整个辅助数组,那么对于时间来说极为浪 费,因此待排数组中最大的数越小,且越贴近待排容量,算法最优 */#include <stdio.h>void sort_ages(int ages[], int len){ if(ages == NULL || len < 1) return ; const int max_age = 100; int age_counts[max_age + 1]; for(int i = 1; i < max_age + 1; ++i) age_counts[i] = 0; for(int i = 0; i < len; ++i) // 统计各年龄出现的 ++age_counts[ages[i]]; for(int i = 1, index = 0; i <= max_age; ++i) { for(int j = 0; j < age_counts[i]; ++j) { ages[index++] = i; } }}int main(){ int ages[] = {33, 66, 77, 45, 33, 100}; sort_ages(ages, 6); for(int i = 0; i < 6; ++i) printf("%d ", ages[i]);} 运行结果: 33 33 45 66 77 100