堆排序也是一种选择排序，对序列的原始顺序不敏感，适用于数据量大的情况。1. 算法思想 ...
堆排序也是一种选择排序，对序列的原始顺序不敏感，适用于数据量大的情况。
1. 算法思想
堆：子节点的值总是小于/大于它的父节点。这里使用的是最大堆。
将数组转化为最大堆，依次将对顶元素取出，与堆中最后一个元素交换，堆长度减一，对堆作调整；如此循环至堆为空，最后得到一个元素由小到大排列的数组。
2. 时间复杂度
最好情况 O(nlogn)：初始化建堆复杂度O(n)（建堆过程中每个元素最多比较2次，平均交换1次）；每次弹出后调整时间O(logn)，弹出n-1次最坏情况 O(nlogn)：数据顺序对排序效率无影响
3. 空间复杂度 O(1)
就地排序，辅助空间为常数级
4. 稳定性
不稳定。存在不相邻交换
5. 代码实现（C语言）
首先是针对给定位置元素调整堆的代码，在堆化和排序过程中都要调用：void ShiftDown(int *A, int pos, int len){ int i, maxInd, tmp; i = pos; while (i <= (len - 2) / 2) { maxInd = i; if ((i * 2 + 1) < len && A[maxInd] < A[i * 2 + 1]) { maxInd = i * 2 + 1; } if ((i * 2 + 2) < len && A[maxInd] < A[i * 2 + 2]) { maxInd = i * 2 + 2; } if (maxInd != i) { tmp = A[i]; A[i] = A[maxInd]; A[maxInd] = tmp; i = maxInd; } else { break; } }} 然后是数组初始化（堆化）的代码：void Heapfy(int *A, int n){ int i; for (i = (n - 2) / 2; i >= 0; --i) { ShiftDown(A, i, n); }} 最后是堆排序的过程：void HeapSort(int *A, int n){ int i; int tmp; Heapfy(A, n); for (i = n - 1; i > 0; --i) { tmp = A[0]; A[0] = A[i]; A[i] = tmp; ShiftDown(A, 0, i); }}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
