【C数据结构】堆排序和选择排序

【C数据结构】堆排序和选择排序,第1张

文章目录
    • 一、选择排序
      • 1、选择排序的思路
      • 2、选择排序的代码实现
    • 二、堆排序
      • 1、什么是堆排序
      • 2、堆结点中的关系
      • 3、堆的建立
      • 4、堆的升序和降序

一、选择排序 1、选择排序的思路

在这里为了更高的效率,一次固定两个值的位置,在最开始找到最小值和最大值并固定其位置。


特殊情况注意:


2、选择排序的代码实现
//直接选择排序
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//找到最大和最小值。
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end; i++) 
		{
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
			if (a[mini] > a[i])
			{
				mini = i;
			}
		}
		//分别将最小值和最大值固定在begin和end位置
		Swap(&a[begin], &a[mini]);
		if (a[begin] == a[maxi])//特殊情况处理
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++; end--;
	}
}


二、堆排序 1、什么是堆排序

在数据结构中,堆的逻辑结构是一个完全二叉树,而物理结构是一个数组。

堆有两个特性
结构性:是用数组表示的完全二叉树
有序性:任意结点的值,都大于或者小于其子树上的结点值
    最大堆:任意结点值都大于其子树上所有的结点值
    最小堆:任意结点值都小于其子树上所有的结点值

如以下就是一个小堆。

逻辑结构:


2、堆结点中的关系

在下标关系中可以推出
leftchild=parent2+1
rightchild=parent
2+2
不管是左孩子还是右孩子都有:(child-1)/2=parent

所以凭借这个关系,可以很规律的访问其它子结点。


3、堆的建立

向下调整算法:
前提:根的左右子树都是小堆或者大堆。
接下来都以小堆为目标,小堆的实现和大堆的实现方法都一样
比如这个以27为根的左子树和右子树都是小堆。

如果需要将这个树建立成一个小堆。

所以在向下调整算法中,从根开始的代码为:

//向下调整算法
//a指向数组首地址,n为数组中数的数量
void AdjustDown(int* a, int n)
{
	int parent = 0;	//从根结点开始
	int child = parent * 2 + 1;	//先从左孩子开始访问
	while (child < n)  //child最大为n-1
	{
		if (child + 1 < n && a[child] > a[child + 1]) //如果右孩子小于左孩子 就访问右孩子,并且保证child+1不能越界
		{
			child += 1;
		}
		if (a[parent] > a[child]) //如果父亲大于孩子,交换
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;  //父亲小于孩子,向下调整完成。
		}
	}
}



而当左右子树都不为小堆那该怎么办呢?
我们可以把单独一个叶结点看作一个小堆,从叶结点的父节点开始通过多次向下调整算法。

//向下调整算法,每次规定了parent的位置
void AdjustDown(int* a, int n, int i)
{
	int parent = i;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1]) // >建小堆,<建大堆
		{
			child += 1;
		}
		if (a[parent] > a[child]) // >建小堆,<建大堆
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//建堆
void HeapSort(int* a, int n)
{
	//建堆 O(N)
	//i的初始值从最后一个结点n-1,再通过parent=(child-1)/2得到第一个父亲结点位置,一直到第一个根节点i=0
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) 
	{
		AdjustDown(a, n, i);
	}
}

现在我们实现了随便给一组数组,我们都可以建立一个小堆或者一个大堆。
接下来如果实现数组的升序和降序呢?


4、堆的升序和降序

接下来介绍实现升序,因为升序和降序的大致思路一样。
堆也是通过选择排序进行选数

先让我们明白一下,通过大堆和小堆我们可以分别得到什么?
在大堆中,最顶上的就是最大的数,在小堆中,最顶上的就是最小的数。

如果为了实现升序,选择了小堆。

而如果为了实现升序,选择了大堆。


代码实现:
升序用大堆实现

//升序用大堆

//调整为大堆
void AdjustDown(int* a, int n, int i)
{
	int parent = i;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1]) // >建小堆,<建大堆
		{
			child += 1;
		}
		if (a[parent] < a[child])  // >建小堆,<建大堆
		{
			Swap(&a[parent], &a[child]); 
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapSort(int* a, int n)
{
	//建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	//升序
	int end = n - 1; //从最后一个位置开始
	while (end > 0)
	{
		Swap(&a[0], &a[end]); //将最大值放在end位置
		AdjustDown(a, end, 0); //重新调整为大堆,parent=0为标准的向下调整算法
		--end; //最后一个位置减一,固定这次最大值位置,并且使得根的左右子树都是大堆,使得可以用向下调整算法。
	}
}

所以
实现升序:先通过向下调整算法建立大堆,再在大堆中通过选择排序实现升序。
实现降序:先通过向下调整算法建立小堆,再在小堆中通过选择排序实现升序。

堆排序的时间复杂度:
每次建堆最大调整高度次logN,而有n个数,总的时间复杂度就是O(N*logN)。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/867056.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-12
下一篇 2022-05-12

发表评论

登录后才能评论

评论列表(0条)

保存