数据结构第九天（堆排序）

前言

概述

源码：

主函数：

运行结果：

其他

前言

哈哈，这个堆排序算法很久之前就已经敲过一遍了，时间一久，思路有点淡忘。今天重新看过一遍之后，又亲自撸代码，幸运的是，代码运行一次就成功了，没有任何逻辑错误而且结果也达到了预期效果。

在最后，与大家共勉：你所走的每一步路，都算数。

概述

堆排序（Heap Sort）是一种基于比较的排序算法，使用二叉堆（Binary Heap）数据结构来帮助实现其排序过程。二叉堆可以被视为一颗完全二叉树，其中每个节点的值都不大于（或不小于）其子节点的值，这样的二叉堆分别称为最大堆（Max Heap）和最小堆（Min Heap）。堆排序主要包括两个步骤：建堆（构造初始堆）和调整堆。

1. 建堆（构造初始堆）

首先，将待排序的序列构造成一个最大堆，即所有父节点的值都大于或等于子节点的值。这一步的目的是选出最大的元素（位于根节点），准备将它与序列的末尾元素交换。

建堆的过程从最后一个非叶子节点开始，向前逐个对每个父节点进行调整，确保每个父节点的值都大于其子节点的值。最后一个非叶子节点的位置可以通过序列长度计算得出，设序列长度为n，则最后一个非叶子节点的位置是n/2 - 1（假定序列的起始索引为0）。

2. 调整堆

将最大堆的根节点（即当前最大值）与最后一个元素交换，然后减少堆的大小，对新的根节点执行下沉操作，以重新满足最大堆的性质。重复这个过程，直到堆的大小为1，排序完成。

下沉操作指的是将新的根节点值与其子节点中较大者交换，直到该节点值大于其子节点或已经到达叶子节点。

堆排序的算法步骤

建立最大堆：从最后一个非叶子节点开始，向上进行调整，确保每个父节点都大于其子节点。
排序：
- 将根节点（最大值）与最后一个元素交换，此时序列的最后部分已经是排序好的。
- 减少堆的大小（排除已排序的部分），对新的根节点进行下沉操作，以维护最大堆的性质。
- 重复上述过程，直到堆的大小为1。

时间复杂度

最好、最坏、平均情况下的时间复杂度均为O(n log n)。
堆排序的空间复杂度为O(1)，因为它是原地排序算法。

特点

不稳定排序：相同的元素可能会因为堆调整过程而改变其相对位置。
原地排序：不需要额外的存储空间。

堆排序是一种高效的排序算法，尤其适用于数据量大的情况。由于其在最坏情况下也能保持O(n log n)的时间复杂度，因此是一种非常可靠的排序方法。

源码：

void heapAdjust(int* dest,  unsigned int dataCnt)
{
	unsigned int head = dataCnt;
	head /= 2;
	if (head * 2 + 1 == dataCnt)
	{
		if (*(dest + head * 2) > *(dest + head * 2 - 1))
		{
			if (*(dest + head - 1) > *(dest + head * 2 - 1))
			{
				swap(*(dest + head - 1), *(dest + head * 2 - 1));
			}
		}
		else if (*(dest + head - 1) > *(dest + head * 2))
		{
			swap(*(dest + head - 1), *(dest + head * 2));
		}
	}
	else{
		if (*(dest + head -1) > *(dest + head * 2 - 1))
		{
			swap(*(dest + head - 1), *(dest + head * 2-1));
		}
	}
	
	for (int i = dataCnt/2-1; i > 0; --i)
	{
		head = i;
		if (*(dest + head * 2) > *(dest + head * 2 - 1))
		{
			if (*(dest + head - 1) > *(dest + head * 2 - 1))
			{
				swap(*(dest + head - 1), *(dest + head * 2 - 1));
			}
		}
		else if (*(dest + head - 1) > *(dest + head * 2))
		{
			swap(*(dest + head - 1), *(dest + head * 2));
		}
		
	}
	
}
void sortByHeapSort(int* dest, const unsigned int dataCnt)
{
	for (int i = 0; i < dataCnt; ++i)
	{
		heapAdjust(dest + i, dataCnt - i);
	}
}

主函数：

#include<stdio.h>
#include<iostream>
using namespace std;
#include"dataStructAPI.h"
#include"sort.h"
#include<windows.h>
int main()
{

int array[16] = { 0 };
   numberProducer.getFilledArray(array,16);
   cout << " 原始数据：";
   numberProducer.showArray(array,16);

   sortByHeapSort(array, 16);
   cout << " 堆排序后：";
   numberProducer.showArray(array, 16);

   sortBySelectSort(array, 16);
   cout << "选择排序后：";
   numberProducer.showArray(array, 16);

   sortByQuickSort(array, 16);
   cout << "快速排序后：";
   numberProducer.showArray(array, 16);

   sortByBubbleSort(array, 16);
   cout << "冒泡排序后：";
   numberProducer.showArray(array, 16);

   sortByShellInsert(array, 16, 3);
   cout << "希尔插入排序后：";
   numberProducer.showArray(array, 16);

   sortByBinarySearchInsert(array, 16);
   cout << "折半插入排序后：";
   numberProducer.showArray(array, 16);

   sortByDirectInsert(array, 16);
   cout << "直接插入排序后：";
   numberProducer.showArray(array, 16);

   system("pause");
   return 0;
}