前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >选择排序(简单选择排序、堆排序)

选择排序(简单选择排序、堆排序)

作者头像
跋扈洋
发布2021-09-03 14:11:22
5210
发布2021-09-03 14:11:22
举报
文章被收录于专栏:物联网知识物联网知识

选择排序

选择排序的基本思想是:每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列。

简单选择排序

概念

假设排序表为L[1…N],,第i趟排序即从L[1…N]中选择关键字最小的元素与L(i)交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可以使得整个排序表有序。

算法实现

代码语言:javascript
复制
void select_sort(ElemType A[],int n)
{
	int i, j,min;
	for (i = 0; i < n-1; i++)
	{
		min = i;	//	记录最小元素位置
		for (j = i + 1; j < n; j++)	//在A【i...n-1】中选取最小的元素
			if (A[j] < A[min])
				min = j;			//更新最小元素位置
		if (min != i)
			swap(A[i],A[min]);		
	}
}

堆排序

概念

  1. 堆排序要结合顺序存储的完全二叉树的特性进行学习。 对于完全二叉树而言:
  • 结点 i 的左孩子是 2i
  • 结点 i 的右孩子是 2i+1
  • 结点 i 的父节点是 i/2
  • 编号 <= n/2的结点都是分支结点
  1. n个关键字序列L[1…N]称为堆。 当且仅当 L(i) >=L(2i) 且 L(i)>=L(2i+1) 可以将该一维数组视为一棵完全二叉树,满足此条件的堆称之为大根堆。大根堆的最大元素存放在根节点,且其任一非根节点的值小于等于其双亲结点值。 小根堆反之。
  2. 堆排序的思路很简单:首先将存放在L[1…N]中的N个元素建成初始堆,由于堆本身的特点(以大根堆为例),堆顶元素就是最大值。输出堆顶元素后,通常将堆底元素送入堆顶,此时根节点已不满足大顶堆的性质,对被破坏,将堆顶元素向下调整使其继续保持大顶堆的性质,再输出堆顶元素。如此重复,直到堆中仅剩一个元素为止。
  3. 构建初始堆的方法:先对完全二叉树的最右下边的子树调整,使其成为堆(如果此节点的孩子有比他大的,则将最大的孩子和父节点调换),之后向前依次对各节点([N/2]-1~1)为根的子树进行筛选,看该节点是否大于其左右孩子的值,若不大于则交换,交换后可能会破坏下一级的堆,于是采用上述方法继续构建下一级的堆,直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆,直到根节点。

算法实现

代码语言:javascript
复制
void Build_Max_Heap(ElemType A[],int len)
{	//构建大根堆
	int i;
	for (int i = len / 2; i > 0; i--)	//从i=[n/2]~1,反复调整堆
		HeadAdjust(A,i,len);
}

void HeadAdjust(ElemType A[],int k,int len)
{//将元素k为根的子树进行调整
	int i;
	A[0] = A[k];	//A[0]暂存子树的根节点
	for (i = 2 * k; i <= len; i*=2) //沿key较大的子节点向下筛选
	{
		if (i < len && A[i] < A[i + 1])
		{
			i++;	//取较大的子节点的下标
		}
		if (A[0] >= A[i])
			break;	//筛选结束
		else
		{
			A[k] = A[i];//将A[i]调整到双亲结点上
			k = i;//修改k值,以便继续向下筛选
		}
	}
	A[k] = A[0];	//被筛选结点的值放入最终位置
}

void Heap_Sort(ElemType A[],int len)
{//堆排序
	int i;
	Build_Max_Heap(A,len);//初始建堆
	for (i = len; i > 1; i++)	//n-1趟的交换和建堆过程
	{
		swap(A[i],A[1]);	//输出堆顶元素(和堆底元素互换)
		HeadAdjust(A,1,i-1);//调整,把剩余的i-1个元素整理成堆
	}
}

物联网知识

点个在看你最好看

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 物联网知识 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档