堆排序
堆排序是在堆数据结构上执行的。我们知道堆是一个完整的二叉树。堆树可以有两种类型。最小堆或最大堆。对于最小堆，根元素最小，对于最大堆，根元素最大。形成堆之后，我们可以从根中删除一个元素并将最后一个元素发送到根。完成这些交换过程后，我们需要重新堆放整个数组。通过从根目录删除元素，我们可以对整个数组进行排序。
堆排序技术的复杂性
时间复杂度：O（nlogn）
空间复杂度： O(1)
输入输出
Input: A list of unsorted data: 30 8 99 11 24 39 Output: Array before Sorting: 30 8 99 11 24 39 Array after Sorting: 8 11 24 30 39 99
算法
heapify（数组，大小）
输入- 数据数组，以及数组中的总数
输出- 使用数组元素的最大堆
Begin
for i := 1 to size do
node := i
par := floor (node / 2)
while par >= 1 do
if array[par] < array[node] then
swap array[par] with array[node]
node := par
par := floor (node / 2)
done
done
EndheapSort（数组，大小）
输入： 数据数组，数组中的总数
输出-nbsp;排序数组
Begin
for i := n to 1 decrease by 1 do
heapify(array, i)
swap array[1] with array[i]
done
End示例
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 1; i<=size; i++)
cout << array[i] << " ";
cout << endl;
}
void heapify(int *array, int n) {
int i, par, l, r, node;
//创建最大堆
for(i = 1; i<= n; i++) {
node = i; par = (int)node/2;
while(par >= 1) {
//如果新节点大于父节点，则交换
if(array[par] < array[node])
swap(array[par], array[node]);
node = par;
par = (int)node/2;//update parent to check
}
}
}
void heapSort(int *array, int n) {
int i;
for(i = n; i>= 1; i--) {
heapify(array, i);//heapify each time
swap(array[1], array[i]);//swap last element with first
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n+1]; //effective index starts from i = 1.
cout << "输入元素：" << endl;
for(int i = 1; i<=n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
heapSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}输出结果
Enter the number of elements: 6 输入元素： 30 8 99 11 24 39 Array before Sorting: 30 8 99 11 24 39 Array after Sorting: 8 11 24 30 39 99