计数排序（排序终篇）

1.计数排序

2.排序的稳定性

1.计数排序

1.1计数排序的概念

计数排序就是把要排序的数组的里面的数据在有序的数组中记录次数，每个数据有多少个就在另一个数组(有序的)上对应的位置加多少，有俩个2就在有序的数组下标2的位置标2，最后把有序数组的元素按顺序一个一个搬过来，这样就把数组排好了。

1.2代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}

	}
	int range = max - min + 1;//知道俩个边界求中间有多少个，右-左+1
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail:");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}
int main()
{
	int a[] = {9,1,8,2,7,3,6,4,5};
	int size = sizeof(a) / sizeof(a[0]);
	//InsertSort(a, size);
	//ShellSort(a, size);
	//MergeNonR(a, size);
	//SelectSort(a, size);
	CountSort(a, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

 代码分析：
第一个for是去找到最大值和最小值为了获得边界值，而且用calloc还需要找到有多少个元素，第三个for是去计数,a[i]-min就是一个相对值，因为开辟的空间是从最小到最大都有，假设100是最低值也就是下标为0，那么101就是100后面一个下标为1，a[i]-min就是去得到count的下标，有了下标才能给对应的位置计数，最后一个for就是把count中计数大于0的位置把i+min放到数组alm，因为a[i]-min=下标,那么a[i]=下标+min就是对应的值，这里while里面的条件是count[i]--，如果一开始是0就不会进，是1则进去后就变为0，这个是原数组有重复的数据。

1.3计数排序的时间复杂度

第一个for遍历了原数组N次，最后一个for循环遍历了开辟的数组range次，则总的时间复杂度为O(N+range)

1.4计数排序的缺陷

计数排序适合整数于范围集中的，因为是在开辟的数组是计数，如果不是整数不好记录，范围如果不集中则会开辟很多空间，但是很多空间用不上就会造成空间浪费。

2.排序的稳定性

稳定性：相同的值相对顺序不变 

排序的稳定性简单来说，在排排队中，A和B一样高，A站在B前 ，排完后，若A还是在B前面则就是稳定性好，A在B后面则就不稳定，在上面的排序中一般复杂的排序都不稳定，像堆排序，希尔排序快速排序，堆排序若一样大的数字在不同子树，则在先上或者向下调整的过程中就容易发生本来在B前面，调整完后到B后面去了，希尔设置gap组就有可能一样大的数据在不同gap组里面，这样也容易发生上面的情况，而快速排序在全是一样的数据中，最后会把相遇的地方于第一个交换这样就不稳定了。