计数排序详解

前言：这篇文章会给大家把计数排序安排的明明白白，详细的讲解计数排序的原理

例子：现在我有一个数组不知道里面到底有多少个元素，但是我要把它进行排序，怎么排序呢？

我先随便拿一个数组（你假装你不知道里面的元素个数和元素）

int arr[5] = {1000,1001,1008,1007,1009}

然后我们需要找到这个数组的最大值和最小值的差值，然后得出一个闭区间，就是每两个数之间的差值的绝对值就是在这个范围里面也就是[0，max-min]

找到范围后，再做什么呢？

再就是把这个范围进行拓宽成一个整型数组

1000到1009是10个元素

这个数组全部初始化为0

也就是int a[10]={0,0,0,0,0,0,0,0,0,0}

? ? ? ?对应下标? ? ?0 1 2 3 4 5 6 7 8 9

我们找每一个元素-min得出来的差值，这个差值就是a数组每一个对应的下标，每找出来一个差值就对应的a[i]++

之后数组变成了int a[10]={1,1,0,0,0,0,0,1,1,1}

然后我们怎么把原数组进行排序呢？

a数组中计数为0的就把它滤掉，就是不存在这个数，然后直到找到有这个数

所以我们可以用一个循环来解决了

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n = 0;
	//自行输入一个数代表数组的元素个数
	scanf("%d", &n);
	//VS不支持变长数组，所以我们把这个数组调大一些，以免越界
	int arr[100] = { 0 };
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	//输入完后开始找最大最小值了
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (max < arr[i])
			max = arr[i];
		if (min > arr[i])
			min = arr[i];
	}
	int sub = max - min + 1;//求范围
	int* p = (int*)calloc(sizeof(int),sub);
	//判断一下
	if (p == NULL)
	{
		perror("calloc");
		return 1;
	}
	//计数
	for (int i = 0; i < n; i++)
	{
		p[arr[i] - min]++;
	}
	//计数完成后，再对原数组进行重新排序就行了
	int k = 0;//定义一个k变量对原数组进行输入数字
	int j = 0;
	for (j = 0; j < sub; j++)
	{
		while (p[j]--)
		{
			arr[k++] = j + min;
		}
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	free(p);
	p = NULL;
	return 0;
}