JavaScript 中的排序算法：使用 ECMAScript 2021 实现 heap-sort

排序算法是计算机科学中的基础算法之一，其目的是将未排序的数据序列按照某种规则进行排序。在前端开发中，排序算法可以帮助我们对一些数据进行排序，从而实现更好的数据展示效果或者其他需求。

本文中，我们将会介绍一种 ECMAScript 2021 中新增的排序算法——heap-sort，该算法是一种基于二叉堆的排序算法，其时间复杂度为 O(nlogn)，是一种非常实用的排序算法。

二叉堆

在介绍 heap-sort 算法之前，我们需要先了解一下二叉堆这个数据结构。

二叉堆是一种完全二叉树，同时也是一种优先队列，堆的每一个节点都比其左右子节点要小（或大）。通过这种方式组织数据可以让我们实现高效的数据插入、删除和查找操作。

在 JavaScript 中，我们可以通过数组来模拟二叉堆的数据结构，对于一个下标为 i 的节点，其对应的左子节点和右子节点的下标分别为 2i+1 和 2i+2。因此，我们可以使用下面的代码来实现一个二叉堆：

class Heap {
  constructor() {
    this.heap = [];
  }

  get size() {
    return this.heap.length;
  }

  insert(value) {
    this.heap.push(value);
    let i = this.size - 1;
    let parent = Math.floor((i - 1) / 2);
    while (i > 0 && this.heap[parent] < this.heap[i]) {
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
      parent = Math.floor((i - 1) / 2);
    }
  }

  remove() {
    const lastIndex = this.size - 1;
    [this.heap[0], this.heap[lastIndex]] = [this.heap[lastIndex], this.heap[0]];
    const result = this.heap.pop();
    let i = 0;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    while (left < this.size) {
      let maxChild = right < this.size && this.heap[right] > this.heap[left] ? right : left;
      if (this.heap[i] < this.heap[maxChild]) {
        [this.heap[i], this.heap[maxChild]] = [this.heap[maxChild], this.heap[i]];
        i = maxChild;
        left = 2 * i + 1;
        right = 2 * i + 2;
      } else {
        break;
      }
    }
    return result;
  }
}

Heap-Sort 算法

有了二叉堆这个数据结构，heap-sort 算法实现就变得比较简单了。其基本思路是将未排序的数据构建成一个二叉堆，然后依次将堆顶元素取出来放到已排序的数组中，取出堆顶元素后需要重新调整堆结构，使得剩余的元素仍然组成一个合法的二叉堆。当所有元素都取完后，已排序的数组就是一个有序数组了。

对于一个长度为 n 的数组，我们可以使用下面的代码来实现 heap-sort 算法：

function heapSort(array) {
  const heap = new Heap();
  array.forEach(value => heap.insert(value));
  const result = [];
  while (heap.size) {
    result.push(heap.remove());
  }
  return result;
}

总结

heap-sort 算法是一种基于二叉堆的排序算法，其时间复杂度为 O(nlogn)，是一种效率较高的排序算法。在 JavaScript 中，我们可以使用 ECMAScript 2021 中的新特性来实现 heap-sort 算法。

除了 heap-sort 算法，还有其他的排序算法，比如冒泡排序、插入排序、选择排序、快速排序等等。每种排序算法都有其自身的优缺点，需要根据实际情况选择合适的算法。希望本文对各位读者在后续的学习和工作中有所帮助。

来源：JavaScript中文网 ，转载请注明来源 本文地址：https://www.javascriptcn.com/post/65a7845dadd4f0e0ff0a6e4e