DS八大排序之直接选择排序和堆排序

这篇具有很好参考价值的文章主要介绍了DS八大排序之直接选择排序和堆排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

上一期我们已经介绍了,排序、为什么要有排序以及排序在实际生活中的应用。并且介绍并实现了直接插入排序和它的优化即希尔排序~!本期我们再来学习一组排序 ---- "选择排序"即直接选择排序和堆排序~!

本期内容介绍

直接选择排序

堆排序

选择排序的基本思想

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

直接选择排序

在元素集合a[i].....a[n-1]中,选择一个最大最小的数据,如果他不是这个序列中的最后一个第一个,则该序列中的最后一个第一个进行交换,将剩余的元素重复上述操作,直到序列的元素只有一个则结束!

OK,举个栗子画个图(这里是以升序距离的):

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

OK,直接选择排序的过程就是这样的,下面我们来实现一下:还是和以前一样,先写单趟再来改造整体:

单趟

int left = begin;//当前序列的最左端
int min = begin;//最小的元素的下标
for (int i = begin; i < n; i++)
{
	if (a[min] > a[i])
		min = i;
}

Swap(&a[left], &a[min]);//最左端的元素与当前序列中最小的元素交换

整体

直接选择排序改造整体也很简单,只需要,让每个元素都重复单趟即可~!

void SelectSort(int* a, int n)
{
	for (int begin = 0; begin < n; begin++)
	{
		int left = begin;//当前序列的最左端
		int min = begin;//最小的元素的下标
		for (int i = begin; i < n; i++)
		{
			if (a[min] > a[i])
				min = i;
		}

		Swap(&a[left], &a[min]);//最左端的元素与当前序列中最小的元素交换
	}
}

OK,测试一下:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

OK,没有问题。这样写实每次找到当前序列中最小的一个,然后与最左端(升序)交换,我们其实可以对他进行一个小优化的--->每次找到当前序列中的两个元素(一个最小,一个最大),最小的与当前序列的最左端交换,最大与当前序列的最右端交换~!

OK,还是先写单趟,在改造多趟:

单趟

int min = begin, max = begin;
for (int i = begin + 1; i <= right; i++)
{
	if (a[min] > a[i])
		min = i;//选出最小

	if (a[max] < a[i])
		max = i;//选出最大
}

Swap(&a[begin], &a[min]);//最小与左端交换
Swap(&a[right], &a[max]);//最大与右端交换

整体

void SelectSort(int* a, int n)
{
	int begin = 0, right = n - 1;
	while (begin < right)
	{
		int min = begin, max = begin;
		for (int i = begin + 1; i <= right; i++)
		{
			if (a[min] > a[i])
				min = i;

			if (a[max] < a[i])
				max = i;
		}

		Swap(&a[begin], &a[min]);
		Swap(&a[right], &a[max]);
		++begin;
		--right;
	}
}

这就是一次选出两个的整体。OK,我们来个栗子测试一下:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

怎么没有实现排序呢?是我们的思想有问题???OK,遇事不慌,调试走起:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

这是调试找到的第一次最大和最小的元素的下标~!然后下来就是最小与左端交换,最大与右端交换,但此时最大恰好在最左端,一执行最小与最左端交换后在在执行在最大与最右交换时发现最大的已经不在原来的位置了~!这就导致了上述的乱序!

解决方案:在交换完最小与最左端后,判断一下最大的位置,如果最大的是在最左端,则此时最大值应该被换到了最小值的位置,因此,我们只需要调整一下最大值是在最小值的位置即可,即max = min~!

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int min = left, max = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[min] > a[i])
				min = i;

			if (a[max] < a[i])
				max = i;
		}

		Swap(&a[left], &a[min]);
		if (max == left)
			max = min;
		Swap(&a[right], &a[max]);
		++left;
		--right;
	}
}

再来测试一下:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

OK,没有问题了~!

复杂度分析

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

单趟无论选择一个还是选择两个,都得遍历一遍,复杂度为O(N),整体还得遍历一遍O(N)

空间复杂度:O(1)

堆排序

堆排序其实在前面的二叉树堆那里已经介绍并实现过了,这来就等于回顾式的再过一遍~!如果想了解堆这种他是具体咋搞的请点击:二叉树的实现

堆排序(Heapsort)是指利用堆,这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据进行实现排序的。

他既然是借助堆来实现的那得有堆,即要建堆。这里有两种建堆的方式:向上调整建堆+向下调整排序,向下调整建堆+向下调整排序!

他排序是采用删除的思想把最大或最小的换到最后,然后对前N-i(i=1,2,3...n)个进行向下调整!
注意:升序建大堆,降序建小堆

OK,举个排序的例子:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

向上调整建堆

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆
	//O(N*lgN)
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
 
	//向下调整排序
	//O(N*lgN)
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

这里的向上调整建堆和上面堆的插入是一个思路!时间复杂度是O(lgN*N),向下调整排序的时间复杂度是:O(N*lgN)---->有n个元素,每排好一个一下下标,也就是上面的删除的思路!

向下调整建堆

void HeapSort(HPDataType* a, int n)
{
	//向下调整建堆
	//O(N)
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	//向下调整排序
	//O(N*lgN)
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

向下调整建堆,就是从倒数第一个元素的父节点开始向下调整为堆!这样越往上层节点的左右子树必定是堆!

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

OK,测试一下:

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

没问题~!

复杂度分析

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

向下调整和向上调整的时间复杂度都是O(logN)即最多调整高度次,但向上调整建堆是O(N*log)而向下调整建堆的O(N)如下图~!删除排序的时间复杂度是O(N*logN),所以综合下来就是O(N*logN)

空间复杂度:O(1)

向下调整建堆时间复杂度推导

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

向上调整建堆时间复杂度推导

DS八大排序之直接选择排序和堆排序,DS初阶,排序算法,数据结构,算法

OK,本期分享就到这里,好兄弟,下期交换排序不见不散~!文章来源地址https://www.toymoban.com/news/detail-761418.html

到了这里,关于DS八大排序之直接选择排序和堆排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包