排序算法:堆排序

icy2003 程序 2020-05-21 10:05:46 112 0条

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点

Sorting_heapsort_anim.gif

算法评价

  • 平均时间复杂度:O(nlogn)
  • 最好情况:O(nlogn)
  • 最坏情况:O(nlogn)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

算法思想

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区。
  2. 将堆顶元素 R1 与最后一个元素 Rn 交换,此时得到新的无序区(R1, R2, …, Rn-1)和新的有序区(Rn),且满足 R[1, 2, …, n-1] <= Rn。
  3. 由于交换后新的堆顶 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);
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。