堆排序是利用了堆这种数据结构的性质来排序,时间复杂度:最好、平均、最坏的时间负载度都是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;
}