栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序算法之选择排序 (简单选择和堆排序)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序算法之选择排序 (简单选择和堆排序)

  个人主页:欢迎大家光临——>沙漠下的胡杨

  各位大帅哥,大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄: 本期重点:选择排序

  希望大家每天都心情愉悦的学习工作。 

今天我们进入排序章节的选择我排序篇,我们本篇主要是讲解简单选择排序和堆排序的回顾。

选择排序的整体思想:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。

简单选择排序:

1. 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素

2. 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换

3. 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

就是找到一些数中的最小的放在前面,然后找到次小的放在最小的后面,遍历一个个比较交换,我们看下示意图:

我们还可以在这个算法的基础上优化,我们可以一次选出最大的和最小的两个数,把最大的放在最后,最小的放在最前面。

代码实现:

代码整体比较简单,我们要注意的是:

我们要注意,如果是下面的情况呢?

void SelectSort(int* a, int n)//选择排序
{
	assert(a);
	int begin = 0;//开始下标
	int end = n - 1; //结束下标
	
	while (begin < end)//如果两者没有相遇或错过就继续
	{
		int mini = begin;//最小值下标
		int maxi = begin;//最大值下标

		
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i]>a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		//如果交换完,刚好交换的位置是下一次要交换的,我们就手动改变一下
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}
直接选择排序分析:

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用

2. 时间复杂度:O(N^2)

3. 空间复杂度:O(1)

4. 稳定性:不稳定

堆排序: 堆排序思路:

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

堆排序:

我们在二叉树的章节中讲的详细啦,就不在赘述啦,请见  堆排序。

堆排序的分析:

1. 堆排序使用堆来选数,效率就高了很多。

2. 时间复杂度:O(N*logN)

3. 空间复杂度:O(1)

4. 稳定性:不稳定

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/966449.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号