手撕排序算法 - 前端进阶必备

简介：本文将带你了解各种排序算法的时间复杂度，以及它们在实际应用中的优缺点。通过对比和实例，帮助你理解如何选择合适的排序算法，提升前端性能和用户体验。

排序算法是计算机科学中一个重要的分支，它在日常生活中有着广泛的应用。无论是浏览器中的搜索结果、购物车中的商品，还是游戏中的玩家排名，排序算法都在背后发挥着重要作用。了解和掌握排序算法，对于前端开发人员来说，是进阶必备的技能之一。

首先，让我们了解一下时间复杂度。时间复杂度是衡量算法执行时间的重要指标，它可以帮助我们判断算法的效率。常见的排序算法根据时间复杂度可以分为三类：O(n²)、O(n log n)和线性时间复杂度。

O(n²)的排序算法：冒泡排序、选择排序、插入排序等。这些算法在处理大规模数据时效率较低，因为随着数据量的增加，执行时间会急剧增长。在实际应用中，这类算法通常不会用于大规模数据的排序。
O(n log n)的排序算法：快速排序、归并排序、堆排序等。这类算法在处理大规模数据时表现较好，执行时间相对较短。它们通常被用于实际项目中的排序需求，例如在搜索引擎、数据库系统等领域。
线性时间复杂度的排序算法：计数排序、基数排序等。这类算法在处理特定类型的数据时表现优秀，例如小范围的正整数或者按位排序等。但是，它们在实际应用中受到数据范围和数据类型的限制，使用场景相对较少。

接下来，我们将通过实例来详细了解几种常见的排序算法。

冒泡排序：冒泡排序是一种简单的交换排序算法，它通过不断地比较相邻元素的大小，并将不按顺序的元素交换位置，从而达到排序的目的。冒泡排序的时间复杂度为O(n²)，因此在处理大规模数据时效率较低。

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换位置
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

堆排序：堆排序是一种利用二叉堆数据结构实现的排序算法。它通过构建最大堆或最小堆，然后将堆顶元素与堆尾元素互换，之后将剩余元素重新调整为大顶堆或小顶堆，以此类推，最终实现数组的排序。堆排序的时间复杂度为O(n log n)，在大规模数据排序中表现较好。

```javascript
function heapSort(arr) {
// 构建最大堆
function heapify(arr, n, i) {
let largest = i; // 初始化最大值为i
let left = 2 i + 1; // 左子节点
let right = 2 i + 2; // 右子节点

if (left < n && arr[left] > arr[largest]) {
  largest = left;
}
if (right < n && arr[right] > arr[largest]) {
  largest = right;
}
if (largest !== i) {
  let swap = arr[i];
  arr[i] = arr[largest];
  arr[largest] = swap;
  heapify(arr, n, largest); // 递归调整子树
}

}

let n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i—) {
heapify(arr, n, i); // 构建最大堆
}

// 从堆顶开始取出元素并放到末尾，重新调整堆结构
for (let i = n - 1; i >= 0; i—) {
let temp = arr[0]; // 保存当前最大值到temp中
arr[0] = arr[i]; // 将最后一个元素放到堆顶位置上
arr[i] = temp; // 将temp（即最大值）放到数组末尾的位置上
heapify(arr, i, 0);

手撕排序算法 - 前端进阶必备

最热文章