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

发布时间:2024年01月13日

一、选择排序

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

具体步骤:

  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)
  • 稳定
文章来源:https://blog.csdn.net/2301_77459845/article/details/135565510
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。