堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点
算法评价
- 平均时间复杂度:O(nlogn)
- 最好情况:O(nlogn)
- 最坏情况:O(nlogn)
- 空间复杂度:O(1)
- 稳定性:不稳定
算法思想
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区。
- 将堆顶元素 R1 与最后一个元素 Rn 交换,此时得到新的无序区(R1, R2, …, Rn-1)和新的有序区(Rn),且满足 R[1, 2, …, n-1] <= Rn。
- 由于交换后新的堆顶 R1 可能违反堆的性质,因此需要对当前无序区(R1, R2, …, Rn-1)调整为新堆,然后再次将 R1 与无序区最后一个元素交换,得到新的无序区(R1, R2 …, Rn-2)和新的有序区(Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1,则整个排序过程完成。
代码示例
Javascript
function heapSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
function maxHeapify(array, index, heapSize) {
var iMax,
iLeft,
iRight;
while (true) {
iMax = index;
iLeft = 2 * index + 1;
iRight = 2 * (index + 1);
if (iLeft < heapSize && array[index] < array[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && array[iMax] < array[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
index = iMax;
} else {
break;
}
}
}
function buildMaxHeap(array) {
var i,
iParent = Math.floor(array.length / 2) - 1;
for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, array.length);
}
}
function sort(array) {
buildMaxHeap(array);
for (var i = array.length - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
return array;
}
return sort(array);
}