计数排序(详解)

秒速五厘米 2024-03-23 10:10 10阅读 0赞

#### 计数排序 ####

*  一.基础（绝对位置排序）
 *  二.优化（相对位置排序）

## 一.基础（绝对位置排序） ##

> **计数排序只比较不排序。**

![在这里插入图片描述][2a71cd91372049c08435b7971b6ed893.png]

> **从0到9遍历，遇到几就打印几次。**

![在这里插入图片描述][d6ea1985b9fd434b84185fd8df27d12d.png]

## 二.优化（相对位置排序） ##

> **可以看出上面方法有较大的缺陷，如果有个数据是100000，那么我们就需要开100000大的数组，很明显会降低效率。**

![在这里插入图片描述][9b71c165712f462095dfdc6071c77cbb.png]

> **上面一组数据，我们可以先用最大值减最小值求出范围（9），再用每个数减去最小值再进行映射（0~9）。**

![在这里插入图片描述][b87da113dfdd4ba4928a997bebcbb458.png]

![在这里插入图片描述][7c576358749c493db12328d0d835a72d.png]

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<string.h>
    
    
    void CountSort(int* a,int n)
    {
        
    	//找最大值和最小值
    	int max = a[0], min = a[0];
    	for (int i = 0; i < n; i++)
    	{
        
    		if (a[i] > max)
    			max = a[i];
    		if (a[i] < min)
    			min = a[i];
    	}
    	//找范围并创建数组
    	int range = max - min + 1;
    	int* tmp = (int*)malloc(sizeof(int) * range);
    	if (tmp == NULL)
    	{
        
    		perror("malloc fail\n");
    		return;
    	}
    	memset(tmp, 0, sizeof(int) * range);
    	//开始计数
    	for (int i = 0; i < n; i++)
    	{
        
    		tmp[a[i] - min]++;
    	}
    	//排序
    	int cur = 0;
    	for (int i = 0; i < range; i++)
    	{
        
    		while (tmp[i])
    		{
        
    			a[cur++] = i+min;
    			tmp[i]--;
    		}
    	}
    	free(tmp);
    }
    
    
    
    int main()
    {
        
    	int a[20000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 20; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	CountSort(a, 20);
    	/*for (int i = 0; i < 4; i++)
    		printf("%d ", a[i]);*/
    	int st = 0;
    	for (int i = 0; i < 18; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    	return 0;
    }

[2a71cd91372049c08435b7971b6ed893.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/09e1bd863ce64c34b56ded95d3668766.png
[d6ea1985b9fd434b84185fd8df27d12d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6cb19498ab0b46a385eddd61cae142d1.png
[9b71c165712f462095dfdc6071c77cbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9758b06c830c411f9cd9b6eec456a7e2.png
[b87da113dfdd4ba4928a997bebcbb458.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/5e44c235765e4df0983428e76abf413c.png
[7c576358749c493db12328d0d835a72d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/a5b927cf33a847858bcda57d1be1adf8.png