【算法】- 排序 - 堆排序

前言

编译语言：C++
编译器：VS2022

一、堆排序思想

堆排序的思想也就是将数列转化成大顶堆数列，通过充分利用大顶堆数列的特点，第一个数是整个数组的最大值，将这个数放大数列的最后一个位置，这样也就完成了一个位置排序，然后再次调整数列成为堆排序，然后循环这样就可以就可以完成对数列的排序

二、堆排序

#define MAXSIZE 10//数组要排序的个数
#include <iostream>
using namespace std;
//交换
void Swap(int arr[], int n, int m)
{
	int tmp = arr[n];
	arr[n] = arr[m];
	arr[m] = tmp;
}
//调整为大顶堆排序
void HeapAdjust(int arr[], int s, int n)
{
	int j;
	arr[0] = arr[s];//存放双亲结点的值
	for (j = 2 * s; j <= n; j*=2)//找到双亲的所有左孩子结点
	{
		if (j<n && arr[j] < arr[j + 1])//如果右孩子比左孩子大则j加1,且在序列内
			j++;
		if (arr[s] >= arr[j])//如果双亲比孩子结点都大则直接返回,且在序列内
			break;
		arr[s] = arr[j];//将比双亲大的孩子赋值给双亲
		s = j;//将j下标给s,找到要交换的孩子结点
	}
	arr[s] = arr[0];//将孩子和双亲完成交换
}
//堆排序
void HeapSort(int arr[])
{
	int i;
	for (i = MAXSIZE / 2; i > 0; i--)//找到每个有孩子的双亲(这里是层序排列完全二叉树)
		HeapAdjust(arr, i, MAXSIZE);//将无序的数列调整为大顶堆
	for (i = MAXSIZE; i > 1; i--)//从数列最后一个数开始循环
	{
		Swap(arr, 1, i);//交换每个大顶堆第一个数和最后一个数
		HeapAdjust(arr, 1, i-1);//再次调整为大顶堆
	}
}
int main()
{
	int i;
	int arr[MAXSIZE + 1] = { 0,5,2,3,7,8,6,1,9,10,4 };//创建要排序数组
	HeapSort(arr);//进行堆排序

	for (i = 1; i <= MAXSIZE; i++)
		cout << arr[i] << " ";
	return 0;
}

总结

时间复杂度O(nlogn)