本文共 1557 字，大约阅读时间需要 5 分钟。

参考极客时间

堆排序

时间复杂度：$O(nlogn)$，但是实际软开中，快排性能更好。

堆性质：

• 堆必须是完全二叉树(保证利用数组存储堆时，由下标i快速找到父节点$(i-1)/2$，左右子节点$2\ast i+1,2\ast i+2$)
• 堆中每个节点必须大于等于(小于等于)子节点
• 支持插入、删除堆顶元素(并且要堆化)
• 如果数组存储n个元素，最后一个非叶子节点下标为$n/2-1$

堆排序(从小到大，利用最大堆和数组)

1. 从后往前堆化数组元素，此时最大元素在首位置
2. 交换元素
3. 堆化

代码

#include 
   
    #include 
    
     using namespace std;void HeapSort(int* array, int n);void buildHeap_(int* array, int n);//建立最大堆void heapify_(int* array, int n, int idx);//调整idx节点满足堆性质void swap_(int* array, int aIdx, int bIdx);void HeapSort(int* array, int n) {   	if (array == nullptr || n <= 1)		return;	buildHeap_(array, n);	int idx = n - 1;	while (idx >= 0) {   		swap_(array, 0, idx);		idx--;		heapify_(array, idx + 1, 0);//堆化堆顶元素	}}void buildHeap_(int* array, int n) {   	//从最后一个非叶子节点从后往前开始堆化	for (int i = n / 2 - 1; i >= 0; i--)		heapify_(array, n, i);//堆化i节点}void heapify_(int* array, int n, int idx) {   	while (true) {   		int leftChildIdx = 2 * idx + 1;		int rightChildIdx = 2 * idx + 2;		int maxIdx = idx;		if (leftChildIdx < n && array[leftChildIdx] > array[maxIdx])			maxIdx = leftChildIdx;		if (rightChildIdx < n&& array[rightChildIdx] > array[maxIdx])			maxIdx = rightChildIdx;		if (maxIdx == idx)			break;		swap_(array, idx, maxIdx);		idx = maxIdx;	}}void swap_(int * array, int a, int b){   	int tmp = array[a];	array[a] = array[b];	array[b] = tmp;}int main() {   	int array[9] = {    7,5,19,8,4,1,20,13,16 };	HeapSort(array, 9);	for (auto i : array)		cout << i << " ";	cout << endl;	getchar();	return 0;}