排序算法常用于对数组进行排序操作，在前端领域也是非常重要的一类算法。本文将详细介绍前端工程中常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。每种排序算法都将包括详细的讲解和代码示例，以便读者更好地理解和掌握排序算法的核心思想和实现方法。

冒泡排序

冒泡排序是一种比较简单的排序算法，其核心思想是依次比较相邻的两个元素，将较大的元素移动到数组的后面，直到整个数组有序。冒泡排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换相邻两个元素的位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(bubbleSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

选择排序

选择排序是一种简单的、不稳定的排序算法。其核心思想是每次遍历数组，选择最小的元素和当前位置进行交换。由于每次迭代只需要交换一次元素，因此选择排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      // 交换当前位置和最小元素的位置
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(selectionSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

插入排序

插入排序是一种简单的、稳定的排序算法。其核心思想是将未排序的元素插入到已排序数组的合适位置。由于插入排序每次只需要将一个元素插入到已排序数组中，因此时间复杂度为 O(n^2)，空间复杂度为 O(1)。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(insertionSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

快速排序

快速排序是一种经典的、高效的、不稳定的排序算法。其核心思想是挑选基准元素，将小于基准元素的值放在左边，大于基准元素的值放在右边，并对左右两个子序列进行递归排序。快速排序越接近最坏情况，性能表现越差。快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(quickSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

归并排序

归并排序是一种经典的、高效的、稳定的排序算法。其核心思想是将数组递归地分为左右两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let i = 0;
  let j = 0;
  const result = [];

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(mergeSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

堆排序

堆排序是一种高效的、不稳定的排序算法。其核心思想是将待排序数组看作一个完全二叉树，并将其转换成一个堆。堆排序分为大根堆和小根堆，在排序时，每次取堆顶元素进行排序。堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

function heapSort(arr) {
  buildMaxHeap(arr);
  for (let i = arr.length - 1; i >= 0; i--) {
    [arr[i], arr[0]] = [arr[0], arr[i]];
    maxHeapify(arr, i, 0);
  }
  return arr;
}

function buildMaxHeap(arr) {
  const len = arr.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    maxHeapify(arr, len, i);
  }
}

function maxHeapify(arr, len, i) {
  let largest = i;
  const left = i * 2 + 1;
  const right = i * 2 + 2;

  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    maxHeapify(arr, len, largest);
  }
}

const numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(heapSort(numbers)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

总结

本文详细介绍了前端开发中常用的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序，每个算法都附带着详细的代码示例和中文注释。读者可以结合具体场景和应用，选择不同的排序算法来解决实际问题。要选择一个合适的排序算法来实现排序，需要综合考虑时间复杂度和空间复杂度，以及实际应用场景中的需求等多个方面的因素。

文章目录