C语言分析基础排序算法——计数排序
目录
计数排序
计数排序基本思路
计数排序改进思路
计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。具体思路为：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
计数排序基本思路
基本思路分析：
//以下面的数组为例
int data[] = { 7,8,9,2,4,5,5,6,3,5 };
void CountSort(int* data, int sz)
{int max = data[0];//遍历数组找出最大值for (int i = 0; i < sz; i++){if (data[i] > max){max = data[i];}}//根据最大值开辟数组int* tmp = (int*)calloc(max + 1, sizeof(int));assert(tmp);//统计数据个数for (int i = 0; i < sz; i++){tmp[data[i]]++;}//按照数据个数写回原数组int j = 0;for (int i = 0; i < (max + 1); i++){while (tmp[i] > 0){data[j] = i;tmp[i]--;j++;}}
}计数排序改进思路
上面的数据如果出现下面的情况：
int data[] = { 100,103,104,105,105,107,109,102 };则不能考虑开辟最大元素+1个元素的空间，因为此时总数据个数小于数组的总长度，造成了空间浪费，可以考虑找出数组中的最大值和最小值，取其差值+1开辟数组，并且此时对应的下标应该是两数之差
//计数排序改进思路
void CountSort_modified(int* data, int sz)
{int max = data[0];int min = data[0];//遍历数组找出最大值for (int i = 0; i < sz; i++){if (data[i] > max){max = data[i];}if (data[i] < min){min = data[i];}}int range = max - min + 1;//根据最大值开辟数组int* tmp = (int*)calloc(range, sizeof(int));assert(tmp);//统计数据个数for (int i = 0; i < sz; i++){tmp[data[i] - min]++;}//按照数据个数写回原数组int j = 0;for (int i = 0; i < range; i++){while (tmp[i] > 0){data[j] = i + min;tmp[i]--;j++;}}
}通过上面的思路解析，很明显计数排序的局限性很大，需要排序的数据必须非常集中，否则不容易计数
计数排序的时间复杂度为O(max(N, range))，空间复杂度为O(range)