堆排序

因為大堆和小堆只能知道最大元素和最小元素
而TopK也只能找出前k個大/小的元素

這一篇，同時滿足上面兩個求

本篇有大量內容在前兩篇文章基礎上：

【資料結構】TopK問題_Rinne’s blog-CSDN博客
【資料結構】堆_Rinne’s blog-CSDN博客

以及很多代碼的介面/函式之前寫過不再重復：

堆 · 凜音Rinne - 碼云 - 開源中國 (gitee.com)

文章目錄

堆排序
- 一、思路
- - 1. 建小堆
  - 2. 建大堆
  - 3. 測驗代碼
- 二、證明時間復雜度
- - 1. 建堆程序
  - 2. 向下調整程序

一、思路

1. 建小堆

排序按從小到大排序，我們可能先需要一個小堆

調整堆的順序有兩種操作方式，向上調整和向下調整

向上調整建小堆：

類似于之前在堆后插入一個數，然后進行向上調整
//堆排序
void Heapsort(int* a, int n)
{
	int i = 0;
	for (i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
}
向下調整建小堆：

調整每一個非葉子節點，將其變成小堆，多個小堆在一起，也就是小堆了

最后一個葉子節點就是最后一個節點的父節點
//向下調整
int i = 0;
for (i = (n - 2) / 2; i >= 0; i--)
{
		AdjustDown(a, n, i);
}

然后就發現，建了一個小堆，再往下操作只能是后面n - 1再進行建堆……這也太麻煩了

變換思路，改建大堆

2. 建大堆

根據之前，pop堆頂元素的原理

在這里插入圖片描述

先把最后一個元素和根交換，再pop掉原來的根，新的根進行向下調整

這里我們不pop掉原來的根，進行向下調整的堆變成前n-1個數的堆里向下調整

在這里插入圖片描述

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

3. 測驗代碼

//堆排序
void Heapsort(int* a, int n)
{
	向上調整
	//int i = 0;
	//for (i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//向下調整
	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 - i - 1, 0);
	}
}

//測驗堆排序
void testsort()
{
	int n = 7;
	int a[7] = { 1, 5, 6, 2, 4, 6, 7 };
	Heapsort(a, n);

	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

}

int main()
{
	testsort();

	return 0;
}