【小小前端】前端排序算法第三期(不简单选择排序-堆排序)

957 阅读3分钟

堆排序(Heap Sort)

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

什么是堆?

堆其实是一种特殊的树。只要满足这两点,它就是一个堆。

  • 堆是一个完全二叉树(除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列)。
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作大顶堆。(正序排序)

对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作小顶堆。(逆序排序)

其中图 1 和 图 2 是大顶堆,图 3 是小顶堆,图 4 不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不同形态的堆。

算法描述

  1. 将待排序序列构建成一个大顶堆,此堆为初始的无序区(其实此时arr[0]已经是最大值,如上图1图2,需要继续对子节点进行排序)
  2. 将堆顶与最后一个元素交换,得到有序序列和无序序列,无序序列的所有元素小于有序序列最小的元素
  3. 交换后堆被破坏,重新构建大顶堆,重复2步骤arr.length - 1 次,此时排序完成;

动图演示

表示一个图压根看不懂(其实两个也看不懂)

代码实现

            let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
            let len = arr.length;
            let heapSort = arr => {
                // 构建大顶堆
                for (let i = Math.trunc(len / 2 - 1); i >= 0; i--) {
                    heapify(arr, i, len);
                }
                // 构建完成之后,对剩余元素继续构建大顶堆
                for (let i = Math.floor(arr.length - 1); i > 0; i--) {
                    // 将根元素(最小或最大元素)与最后一个元素交换
                    swap(arr, 0, i);
                    // 继续进行构建大顶堆
                    heapify(arr, 0, i);
                }
                console.log(arr);
            };
            let swap = (arr, i, j) => {
                let temp;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            };
            // 将 i 结点以下的堆整理为大顶堆,注意这一步实现的基础实际上是:
            // 假设结点 i 以下的子堆已经是一个大顶堆,heapify 函数实现的
            // 功能是实际上是:找到 结点 i 在包括结点 i 的堆中的正确位置。
            // 后面将写一个 for 循环,从第一个非叶子结点开始,对每一个非叶子结点
            // 都执行 heapify 操作,所以就满足了结点 i 以下的子堆已经是一大顶堆
            let heapify = (arr, i, length) => {
                let temp = arr[i];
                for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
                    if (j + 1 < length && arr[j] > arr[j + 1]) {
                        j++;
                    }
                    if (temp > arr[j]) {
                        swap(arr, i, j);
                        i = j;
                    } else {
                        break;
                    }
                }
            };
            heapSort(arr);

结果:

堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是 O(n),排序过程的时间复杂度是 O(nlogn),所以,堆排序整体的时间复杂度是 O(nlogn)。 最佳情况:T(n) = O(nlogn)。 最差情况:T(n) = O(nlogn)。 平均情况:T(n) = O(nlogn)。

另外从堆的行政来看,堆排序是不稳定的排序。

总结

堆排序也是一种选择排序,从名字上乍一看很高深的感觉,但是结合堆的特性来看其实比其他排序更简单(至少比希尔排序简单hhh),重点在于理解什么是堆,以及大顶堆和小顶堆

参考

下期预告

【小小前端】前端排序算法第四期(另一种交换排序之快速排序)