排序的介绍
前面我们学习了插入排序、希尔排序 选择排序 、堆排序 、冒泡排序、快速排序以及归并排序
这些排序都可以在内存中进行排序,不同的是合并排序也可以在磁盘中排序，
怎么在磁盘上排序呢。假设内存只有1G，一个文件里有4G的数据，我们可以通过把这个数据分成4份，每一份我们可以在内存中进行排序，排序好任何写入回去， 然后通过归并排序进行排序好
分配好的每部分先用计数排序进行排序好
计数排序
思路：
遍历一便这个文件数据，统计好这些数值出现的次数，创建一个数组
绝对映射：
找到里面的最大值，以最大值为这个数组的空间，这样很容易造成空间的浪费。
相对映射：
我们可以通过找出其中的最大最小进行相减然后加1，获取到要开辟的大小
我们对每个原数组的元素减去min，然后找到对应的下标的值加1
#include<stdio.h> #include<stdlib.h> #include<assert.h> void CountSort(int* a, int size) { int min = INT_MAX; int max = INT_MIN; int i = 0; //找最大和最小 for (i = 0; i < size; i++) { max = (a[i] > max ? a[i] : max); min = (a[i] < min ? a[i] : min); } int range = max - min + 1; int* newnum = (int*)calloc(range,sizeof(int)); //开始计数 for (i = 0; i < size; i++) { int num = a[i] - min; newnum[num]++; } //开始往原数组覆盖 for (i = 0; i < range; i++) { static int j = 0; while (newnum[i]--) { a[j++] = i + min; } } free(newnum); } int main() { int a[] = { 5,2,6,1,4,8,5,6,2,1,5,6,1,2,4,9,5,4,2,6,4 }; CountSort(a, sizeof(a) / sizeof(a[0])); int i = 0; for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) { printf("%d ", a[i]); } return 0; }
计数排序的优缺点
1.时间复杂度是O（N+ range），要看N和range哪个大
2.适合于整形，且数值相对集中，比如a[10] = {1,200,999999}这个就不能使用了
