利用最小堆/最大堆的性质，将数组中所有元素之间的关系构建成最大堆/最小堆，通过将堆顶元素（即arr[0]）与末尾元素进行交换，此时尾部序列即为有序（最大堆为升序，最小堆为降序），然后对前面的元素（排除已进行过排序的末尾元素）重新构建最大堆/最小堆，因为堆顶元素与末尾元素进行了交换，很有可能造成最大堆/最小堆的性质遭到破坏，而由于只有堆顶元素发生了变化，所以这里可以采用从堆顶向下调整的方法，重新构建最大堆/最小堆
堆排序的时间复杂度为O(NlogN)，空间复杂度为O(1)，算法不稳定
代码如下：
void adjust_down(int arr[],int size)
{
int parent=0;
int child=parent*2+1;
while(child<size)
{
if(child+1<size&&arr[child]<arr[child+1])
swap(arr[child],arr[child+1]);
if(arr[child]<arr[parent])
return ;
swap(arr[child],arr[parent]);
parent=child;
child=child*2+1;
}
}
void GetHeap(int arr[],int size)
{
int start=(size-1)>>1;
while(start>=0)
{
int parent=start;
int child=parent*2+1;
while(child<size)
{
if(child+1<size&&arr[child]<arr[child+1])
swap(arr[child],arr[child+1]);
if(arr[child]>arr[parent])
swap(arr[child],arr[parent]);
parent=child;
child=parent*2+1;
}
start--;
}
}
void HeapSort(int arr[],int size)
{
GetHeap(arr,size);
while(size)
{
swap(arr[0],arr[size-1]);
size--;
adjust_down(arr,size);
}
}
