[数据结构与算法]堆排序heap_sort

堆排序是利用了堆这种数据结构的性质来排序，时间复杂度：最好、平均、最坏的时间复杂度都是O(nlogn)。基本思想是先把无序的数据构建为堆，然后把第一个元素和最后一个元素交换，交换过后，由于原来的堆结构被破坏，所以交换之后要把数据重新构建为堆。

上code

#include <iostream>
#include <algorithm>
using namespace std;

void swap(int& L, int& R)
{
	int tmp = L;
	L = R;
	R = tmp;
}

void heapify(int arr[], int n, int index)
{
	if (index >= n-1)
	{
		return;
	}

	int MAX = index;
	if (2 * index + 1 < n && arr[MAX] < arr[2 * index + 1])
	{
		MAX = 2 * index + 1;
	}
	if (2 * index + 2 < n && arr[MAX] < arr[index * 2 + 2])
	{
		MAX = index * 2 + 2;
	}

	if (MAX != index)
	{
		swap(arr[index], arr[MAX]);
		heapify(arr, n, MAX);
	}
}

void heap_sort(int arr[], int n)
{
	//构建大顶堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) //从第一个非叶子节点开始，往前走，依次构建大根堆
	{
		heapify(arr, n, i);
	}

	//排序
	for (int j = n - 1; j >= 0; --j) 
	{
		swap(arr[0], arr[j]);  //构建好大根堆后，第一个元素就是最大值；交换第一个和最后一个元素
		heapify(arr, j, 0);	   //交换之后，从arr[0]开始维护大根堆。因为其它都已经是大根堆了。
	}
}

int main()
{
	int arr[] = { 2,5,3,1,10,4,20,11,15,8,30,7 };
	int size = sizeof(arr) / sizeof(arr[0]);

	heap_sort(arr, size); //堆排序

	for (int i = 0; i < size; ++i) //打印
	{
		cout << arr[i] << ' ';
	}
	cout << endl;

	return 0;
}