计数排序，基数排序及排序总结

稳定性：当要排序的数组有相同数据时，排序后相同数据的相对位置不变，则称该排序算法稳定，否则即为不稳定.

在这里我在说说计数排序吧，计数排序就是将给定数组中的数进行计数，在从小到大依次输出即可。简单过程如下图所示：

计数排序的时间复杂度：O（N+range），它适用于范围集中的整型数组?

计数排序代码：

void CountSort(int* a, int n)
{
	//先找出数组中的最大值和最小值以便开辟出不会浪费空间的计数数组
	int min = a[0], max = a[0];
	int i;
	for (i = 0; i < n; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
	//通过最大值和最小值确定范围
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	for (i = 0; i < n; i++)
	{
		count[a[i]-min]++;
	}
	int j=0;
    //将改变后的数组传到原数组中
	for (i = 0; i < range; i++)
	{
		while (count[i]--)
		{
            //记得传数时传i+min（相对映射）
			a[j++] =i+min ;
		}
	}
	free(count);

}

?基数排序（桶排序）

思想：分别取出每个数的个位，十位，百位······，每次依次通过个位。十位、百位···对其进行排序

简单过程如下图：

平时这个排序用处不大，在此就不展示它的代码了。