Java教程

【算法】选择排序——堆排序和直接选择排序

本文主要是介绍【算法】选择排序——堆排序和直接选择排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

选择排序

上一篇总结了插入排序:

【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-CSDN博客

这篇接着总结选择排序:

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

后面讲解都以顺序为例

文章目录

  • 选择排序
    • 一、直接选择排序
    • 二、堆排序
    • 三、测试性能

一、直接选择排序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T6NgtSRR-1637133607252)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

按照之前说的遍历一遍只挑出最小然后放最前面,效率有些低

我们可以遍历的时候可以同时找出最大和最小,分别放在beginend,再将 begin++,end--

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8U4GI3x8-1637133607254)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HGDBO1VD-1637133607256)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

以此类推

但如果是遇到begin正好是max的时候,假设我们之前写的是找到min,min先和begin交换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qpsZrIYy-1637133607258)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J213hnM1-1637133607259)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

如果下一步再进行end和max交换会 出错

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J38eceFd-1637133607260)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

所以在max和end交换前,先将min和max的数组下标交换一下,再去交换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MJxHCQvU-1637133607260)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]


这里是以先把大的放后面为例

//选择排序
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	int i = 0;

	while (begin < end)
	{
		int max = begin;
		int min = begin;

		for (i = begin; i <= end; i++)
		{
			if (a[i] > a[max])
			{
				max = i;
			}
			if (a[i] < a[min])
			{
				min = i;
			}
			
		}
		//判断一下begin和end的地方有无min和max
		swap(&a[end], &a[max]);
		if (end == min)
			min = max;

		swap(&a[begin], &a[min]);

		begin++;
		end--;
	}
}


测试代码:

//选择排序测试
void testSelectSort()
{
	int a[] = { 2, 6, 5, 3, 4, 6, 10, 1, 4, 5, 8, 9 };
	int n = sizeof(a) / sizeof(a[0]);
	SelectSort(a, n);
	print(a, n);
}

测试结果:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CmShMLMo-1637133607261)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]


二、堆排序

之前已经介绍过推排序:【数据结构】堆排序_Rinne’s blog-CSDN博客

个人觉得还是重新自己写一遍接口印象更深把

向下调整

//向下调整 
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;

	while (child < n)
	{
		if (a[child] < a[child + 1] && child + 1 < n)
		{
			child++;
		}

		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
            child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆排序

//堆排序
void HeapSort(int* a, int n)
{
	//升序排列,建大堆
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		//向下调整建堆
		AdjustDown(a, n, i);
	}

	for (i = 0; i < n; i++)
	{
		swap(&a[0], &a[n - 1 - i]);
		AdjustDown(a, n - 1 - i, 0);
	}
}

测试结果:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rJDKDgQ8-1637133607261)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images)]

但我不是一次就写成功的,还是会漏一些bug所以还是得多写多练


三、测试性能

在前一篇的基础上测试一下,选择排序和插入排序的性能

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XxGNbpEc-1637133607262)(C:\Users\yujing wang\AppData\Roaming\Typora\typora-user-images.png)]

可以看出,直接插入排序和选择排序差不多,堆排序和希尔排序都很厉害


这篇关于【算法】选择排序——堆排序和直接选择排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!