前端开发者必知：10大经典排序算法全解析

一、引言：排序算法为何重要？

在前端开发中，排序是处理数据集合的基础操作，无论是表格渲染、搜索建议还是数据分析，都离不开高效的排序逻辑。本文将系统梳理10大经典排序算法，从时间复杂度、空间复杂度到稳定性分析，帮助开发者根据场景选择最优方案。

二、算法详解：从原理到实现

1. 冒泡排序（Bubble Sort）

原理：通过相邻元素的比较与交换，将最大值逐步“冒泡”至数组末尾。
实现：

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

性能：

时间复杂度：O(n²)（最坏/平均）
空间复杂度：O(1)
稳定性：稳定（相等元素不交换）
适用场景：小规模数据或教学演示。

2. 选择排序（Selection Sort）

原理：每次选择未排序部分的最小值，与当前位置交换。
实现：

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

性能：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定（交换可能改变相等元素顺序）
适用场景：内存受限环境。

3. 插入排序（Insertion Sort）

原理：将未排序元素插入到已排序部分的正确位置。
实现：

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

性能：

时间复杂度：O(n²)（最坏），O(n)（最优，已排序时）
空间复杂度：O(1)
稳定性：稳定
适用场景：近乎有序的数据。

4. 快速排序（Quick Sort）

原理：分治思想，选择基准值（pivot）将数组分为左右两部分，递归排序。
实现：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivotIdx = partition(arr, left, right);
  quickSort(arr, left, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, right);
  return arr;
}
function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

性能：

时间复杂度：O(n log n)（平均），O(n²)（最坏，如已排序数组）
空间复杂度：O(log n)（递归栈）
稳定性：不稳定
优化：随机选择基准值避免最坏情况。

5. 归并排序（Merge Sort）

原理：分治思想，将数组递归分为两半，分别排序后合并。
实现：

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

性能：

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定
适用场景：大规模数据或链表排序。

6. 堆排序（Heap Sort）

原理：利用堆结构（完全二叉树），先构建最大堆，再逐个提取堆顶元素。
实现：

function heapSort(arr) {
  const 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--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}
function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const 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) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

性能：

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定
适用场景：内存受限的大规模数据。

7. 计数排序（Counting Sort）

原理：统计每个元素的出现次数，按顺序输出。
实现：

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  arr.forEach(num => count[num]++);
  const result = [];
  count.forEach((cnt, num) => {
    for (let i = 0; i < cnt; i++) result.push(num);
  });
  return result;
}

性能：

时间复杂度：O(n + k)（k为数据范围）
空间复杂度：O(n + k)
稳定性：稳定
限制：仅适用于整数且范围较小的数据。

8. 桶排序（Bucket Sort）

原理：将数据分到有限数量的桶中，对每个桶单独排序后合并。
实现（简化版）：

function bucketSort(arr, bucketSize = 5) {
  const buckets = [];
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  for (let i = 0; i < bucketCount; i++) buckets.push([]);
  arr.forEach(num => {
    const idx = Math.floor((num - min) / bucketSize);
    buckets[idx].push(num);
  });
  return buckets.flatMap(bucket => insertionSort(bucket));
}

性能：

时间复杂度：O(n + k)（平均，k为桶数）
空间复杂度：O(n + k)
稳定性：稳定
适用场景：数据均匀分布时效率高。

9. 基数排序（Radix Sort）

原理：按位数从低位到高位依次排序（通常用计数排序作为子过程）。
实现：

function radixSort(arr) {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }
  return arr;
}
function countingSortByDigit(arr, exp) {
  const count = new Array(10).fill(0);
  const output = new Array(arr.length);
  arr.forEach(num => {
    const digit = Math.floor((num / exp) % 10);
    count[digit]++;
  });
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor((arr[i] / exp) % 10);
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  return output;
}

性能：

时间复杂度：O(d(n + k))（d为最大位数，k为基数）
空间复杂度：O(n + k)
稳定性：稳定
适用场景：整数或固定长度的字符串排序。

10. 希尔排序（Shell Sort）

原理：插入排序的改进版，通过分组间隔（gap）逐步缩小范围。
实现：

function shellSort(arr) {
  const n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

性能：

时间复杂度：取决于gap序列，平均O(n^(1.3))
空间复杂度：O(1)
稳定性：不稳定
适用场景：中等规模数据。

三、算法选择指南

小规模数据：插入排序或选择排序（简单且内存友好）。
大规模数据：快速排序（平均最优）或归并排序（稳定但需额外空间）。
特定数据类型：
- 整数且范围小：计数排序/基数排序。
- 均匀分布数据：桶排序。
稳定性需求：归并排序、计数排序、插入排序。

四、总结与建议

掌握排序算法的核心在于理解其时间复杂度、空间复杂度及稳定性。实际开发中，可结合场景选择：

前端表格排序：优先快速排序或内置Array.sort()（多数浏览器已优化）。
大数据量处理：考虑分治或外部排序（如结合Web Worker）。
稳定性要求：避免选择排序和快速排序（可通过额外标记实现稳定，但增加复杂度）。

通过系统学习与实践，开发者能更高效地解决数据排序问题，提升代码质量与性能。