IT小白

这个屌丝很懒，什么也没留下！

热门标签

八大排序之一：堆排序（详解）_堆排序 csdn

作者：IT小白 | 2024-05-24 01:59:35

踩

堆排序 csdn

3、向上/下调整函数（实现堆排序的基本函数）

一、八大排序：

二、堆的基本知识

1、堆的概念

堆是个单调递增/减的满/完全二叉树

如图所示：

每个结点都小于他的孩子结点，我们就称这样的数据结构为小堆

图1是大堆，图2是大堆，图3不是堆（不是完全/满二叉树）

2、堆的构建

建堆的目的大部分是为了排序或者topk问题

不用链表建堆（不好找数据以及移动数据）
用顺序表建堆
采用尾插，不能使用头插
采用头删（此处的头删，指的是删除头处的数值，而不是删除头）

建堆代码：


typedef int HeapDataType;
 
 
typedef struct Heap//构建顺序表
{
	HeapDataType* arr;
	int size;//堆的数据长度
	int capacity;//堆的最大容量
}Heap;

三、堆排序的实现

1、排序原理

利用建大/小堆来找出一组数中的最大/小数据

再多次对剩下的数据继续进行建堆，就可以选出第2大/小的，第3大/小的......(这里需要对根的值进行一个调整，使其不会对剩下的数据产生影响，后续会说明)

2、如何存储&找孩子/父亲结点

任何一个数据都要有一个存储方式，前文提到，堆用顺序表存储

既然要排序，那么找数据就特别关键，而找数据和建堆用的就是父亲节点和孩子结点的一个”比较交换“来实现查找和交换

这里有一个公式：（这里的值都是以下标为准,同时parent和child是相对的）

leftchild==parent*2+1

rightchild==parent*2+2

parent==(child-1)/2 (左右孩子都是这样)

3、向上/下调整函数（实现堆排序的基本函数）

I）向上调整（大堆为例）

孩子和父亲比较，孩子大于父亲就交换

！！该例子不满足向上调整的前提，不能进行向上调整，此处只是为了说明何为向上调整！！

向上调整的前提！！！！！

：该节点的父树是大/小堆，例：

9和5的父亲是7

结点7、2、0构成的结构不是堆，所以不能进行向上调整

II）向下调整（大堆为例）

父亲和孩子比较，父亲小于孩子就交换

向下调整的前提！！！！！

：该节点的子树是大/小堆，例：

7的孩子是9，5

而9，5每个结点的孩子都是NULL，所以构成的结构是堆，能进行向下调整

这里对代码有疑惑不用急，这里只是展示两个函数，具体的步骤后面会补充

代码实现（递归）：


//以下均为建大堆代码
void swap(HeapDataType*p1,HeapDataType*p2)//交换两个结点的值
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
//向上调整建堆
void Adjustup(HeapDataType* arr, int child)//arr是存储数据的顺序表，child是孩子结点的下标
{
	assert(arr);//断言，防止穿空指针
	int parent = (child - 1) / 2;//定位父亲结点
	while (child != 0)//判断结束条件，防止溢出
	{
		if (arr[parent] < arr[child])//如果孩子结点大于父亲结点，就交换。若用>则是建小堆
		{
			swap(&arr[parent], &arr[child]);
		}
		child = parent;
		parent = (child - 1) / 2;
		//孩子和父亲都向上移，进行一轮新的比较
	}
}
 
//向下调整建堆
void Adjustdown(HeapDataType* arr, int parent,int size)//arr是存储数据的顺序表，parent是父节点的下标，size是数组长度
{
	assert(arr);
	int child = parent * 2 + 1;//定位孩子结点
	while (child < size)//判断结束条件，防止溢出
	{
		if (child + 1 < size)//防止下一步的child+1访问越界
		child = arr[child] > arr[child + 1] ? child : child + 1;//判断左右孩子哪一个更大，选取更大的
		if (arr[parent] < arr[child])//如果孩子结点大于父亲结点，就交换
		{
			swap(&arr[parent], &arr[child]);
		}
 
		parent = child;
		child = parent * 2 + 1;
		//孩子和父亲都向下移，进行一轮新的比较
	}
}

4、开始排序

方法1：开辟额外空间

空间复杂度O（n）

I）建堆

以升序：建大堆为例

将一个已知数组的元素依次插入到一个空数组中，每次插入的时候都要进行1次向上调整。

最终就建好了一个大堆，如上图所示。

II）排序

这里我们发现该数组 {10，7，9，2，0，5，1} 并不是有序的，这是因为我们还没有进行排序，只是进行了建堆。

注意：这里排序的过程用到了删除的思想！

Step1：首尾元素交换，然后我们逻辑上把10移出数组。

实际上：{ 1，7，9，2，0，5，10 } 我们认为：{ 1，7，9，2，0，5 }

Step2：对删掉后的剩余数据从arr[0]开始，继续向下调整建堆（因为此时根的子树必然满足堆结构）

建好后的堆是 { 9，7，5，2，0，1 }；

Step3：继续对剩下的元素 {9，7，5，2，0，1} 进行Step1，直到最后数组中 “只剩” 一个元素，此时数组如下

这样我们就排好序了。

可惜这样的排序，不会修改原数组，如果需要修改原数组，则还需要进行一遍覆盖。


int main()
{
	int arr[] = { 2,10,9,7,0,5,1 };//待排序数组
	int arr_sort[7] = { 0 };//用来排序的数组
	int size = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < 7; i++)
	{
		arr_sort[i] = arr[i];//将数组中的元素一个一个传进待排序数组
		Adjustup(arr_sort, i);//每次传进一个元素都进行一次向上调整
	}
	while(size>1)//判断剩余未排元素数量
	{
		swap(&arr_sort[0], &arr_sort[size - 1]);//交换首尾元素
		size--;//“删掉”末尾元素
		Adjustdown(arr_sort, 0, size);//建大堆,将根的元素置成最大
	}
	return 0;
}

方法2：不开辟额外空间（推荐）

空间复杂度O（1）

I）建堆

以升序：建大堆为例

Step1：找到第一个非叶子结点

Step2：以这个结点为开始，对该节点进行向下调整。

Step3：调整完后，再依次向前遍历并调整（每个遍历到的元素都要调整），直到遍历并且调整完前面的所有结点为止

II）排序

Step4：再用方法1的删除思想就可以完成数组的排序了


int main()
{
	int arr[] =  { 2,10,9,7,0,5,1 } ;//待排序数组
	int size = sizeof(arr) / sizeof(arr[0]);
	int start = (size - 2) / 2;//找到第一个非叶子结点
	for(int i=start;i>=0;i--)//遍历完第一个非叶子结点往前的全部
	{
		Adjustdown(arr, i ,size);//每次遍历一个元素时，都要向下调整
	}
	while(size>1)//判断剩余未排元素数量
	{
		swap(&arr[0], &arr[size - 1]);//交换首尾元素
		size--;//“删掉”末尾元素
		Adjustdown(arr, 0, size);//建大堆,将根的元素置成最大
	}
 	return 0;
}