【数据结构】计数排序 _gif图解 _代码实现 _[非比较排序]

缺乏、安全感 2024-04-01 15:06 72阅读 0赞

## 1.计数排序的概念 ##

> 计数排序是一个非比较的[排序算法][Link 1]，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 这是一种**牺牲空间换取时间的做法**，而且当O(k)>O(n*log(n))的时候其效率反而不如归并排序、快排、堆排。*

## 2.排序思想 ##

> **利用数组的索引是有序的，通过将序列中的元素作为索引，其个数作为值放入数组，遍历数组来排序。**

## 3.gif图解 ##

![125cf2150cd64635a872f4fe9f9e8bb2.gif][]

## 4.适用场景 ##

> **数据元素集中(范围小)，数据量大。**

## 5.代码实现 ##

void CountSort(int a[], int len)
    {
    	int max = a[0], min = a[0];
    	for (int i = 1; i < len; i++)
    	{
    		if (a[i] > max)
    		{
    			max = a[i];
    		}
    		if (a[i] < min)
    		{
    			min = a[i];
    		}
    	}
    	int range = max - min;//数据范围为max-min，数据个数为max-min+1
    	int* countArray = (int*)malloc(sizeof(int) * (range + 1));
    	if (countArray == NULL)
    	{
    		perror("malloc()");
    		exit(-1);
    	}
    	for (int i = 0; i < range + 1; i++)
    	{
    		countArray[i] = 0;
    	}
    	for (int i = 0; i < len; i++)
    	{
    		countArray[a[i] - min]++;
    	}
    	//排序
    	int j = 0;
    	for (int i = 0; i <= range; i++)
    	{
    		while (countArray[i]--)
    		{
    			a[j++] = i + min;
    		}
    	}
        free(countArray);//释放空间
    }

开辟数组数据范围\[min，range = max - min\]；数组大小：max - min + 1；

假设max = 109，min = 100；数据范围就是\[100, 109\]，数组大小是10个元素。

**时间复杂度：O(n+k)，k表示数据范围。**

[Link 1]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605?fromModule=lemma_inlink
[125cf2150cd64635a872f4fe9f9e8bb2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fb73a6a4862842caa211341fd1ed7573.gif