【排序篇2】选择排序、计数排序

一、选择排序

整体思想：
从数组中选出最小值和最大值放在起始位置，直到排序完成

具体步骤：

1. 定义两个变量begin和end为下标，指向数组始末
2. 定义要找的最大值的下标为maxi，最小值的下标为mini，刚开始初始化为begin，因为begin和end会缩小，也就是说找最大和最小的范围为当前begin和end之间的范围
3. 找到最大值的下标和最小值的下标，然后把最小值与begin位置的值交换，这里要考虑特殊情况，最后再交换最大值和end位置的值
4. begin++，end–，缩小范围再重复前面的步骤

图示：

代码：

void SelectSort(int* a, int n)
{
   
	//数组的范围
	int begin = 0, end = n - 1;
	while (begin < end)//控制范围
	{
   
		// maxi和mini是下标，从begin开始，因为begin会变化
		int maxi = begin, mini = begin;
		//找最大元素的下标和最小元素的下标
		for (int i = begin; i <= end; i++)//注意找的范围
		{
   
			if (a[i] > a[maxi])
			{
   
				maxi = i;
			}
			if (a[i] < a[mini])
			{
   
				mini = i;
			}
		}
		//最小值与begin的位置交换
		Swap(&a[begin], &a[mini]);
		//特殊情况，如果maxi与begin重叠，此时最大值的下标在mini
		if (begin == maxi)
		{
   
			maxi = mini;
		}
		//最大值与end的位置交换
		Swap(&a[end], &a[maxi]);
		//缩小范围
		++begin;
		--end;
	}
}

特性总结：

• 时间复杂度：O(N ^ 2)
• 空间复杂度：O(1)
• 不稳定

二、计数排序

计数排序采用相对映射的思想，开辟一块空间，该空间的范围为待排序的数组的最大值和最小值之差加1，并且每个元素初始化为0，然后待排序的数组只要是出现的元素就在临时空间对应的位置计数，最后从小到大恢复原来的元素重新放入数组，完成排序。
思路：

1. 在数组中找到最大值max和最小值min
2. 算出最大与最小之间有多少个数，范围range：max-min+1
3. 开临时空间大小为range，每个元素初始化为0
4. 待排序数组的元素减去最小值min即对应临时空间的下标，原数组出现的元素会在临时空间对应的位置计数
5. 从小到大遍历临时空间数组，只要不为0，说明该位置是对应原数组有出现的元素，然后依次重新放入原数组，临时空间的下标加上最小值恢复到原数组的元素的值。

图示：

代码：

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;
	//开空间，每个元素为0，后面要计数
	int* count = (int*)calloc(range, sizeof(int));
	if (count == nullptr)
	{
   
		perror("calloc fail");
		exit(-1);
	}
	//给出现的元素计数
	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;//恢复原来的元素，依次放入数组
		}
	}
	free(count);
}

特性总结：

• 计数排序适用于数据较集中的场景
• 时间复杂度：O(N+range)
• 空间复杂度：O(range)
• 稳定