JavaScript中的10种排序算法：从入门到精通

作为前端开发者，排序算法是我们必须掌握的基础知识。无论是在面试中，还是在实际开发中处理数据展示时，排序都是一个常见需求。今天，我将用通俗易懂的方式，带你了解JavaScript中最常见的10种排序算法。

1. 冒泡排序 - 最直观的排序方式

冒泡排序可能是最容易理解的排序算法了。它的基本思想是：重复地遍历要排序的数组，一次比较两个元素，如果它们的顺序错误就交换它们。

想象一下水中的气泡，较大的气泡会慢慢浮到水面。在冒泡排序中，较大的元素会"冒泡"到数组的末端。

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // 优化：如果一轮没有交换，说明已经有序
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6解构赋值交换元素
        swapped = true;
      }
    }
    if (!swapped) break; // 如果没有发生交换，提前结束
  }
  return arr;
}

特点：

• 时间复杂度：最好情况O(n)(已经有序)，最坏O(n²)
• 空间复杂度：O(1)(原地排序)
• 稳定排序(相等元素不会改变相对位置)

适用场景：数据量小，或者作为学习排序的入门算法。

2. 选择排序 - 每次选择最小的元素

选择排序的思想是：每次从未排序部分选择最小的元素，放到已排序部分的末尾。

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let minIndex = i; // 假设当前索引是最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 找到更小的值，更新索引
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 交换
  }
  return arr;
}

特点：

• 时间复杂度：始终O(n²)
• 空间复杂度：O(1)
• 不稳定排序(可能改变相等元素的相对位置)

适用场景：数据量小，且不要求稳定排序的情况。

3. 插入排序 - 扑克牌排序方式

插入排序类似于我们整理扑克牌的方式：将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i]; // 当前要插入的元素
    let j = i - 1;
    // 将比current大的元素向后移动
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current; // 插入到正确位置
  }
  return arr;
}

特点：

• 时间复杂度：最好O(n)(已经有序)，最坏O(n²)
• 空间复杂度：O(1)
• 稳定排序

适用场景：小规模数据，或者基本有序的数据。

4. 希尔排序 - 插入排序的改进版

希尔排序是插入排序的改进版本，也称为"缩小增量排序"。它通过将原始数组分成若干子序列进行插入排序，然后逐步缩小增量直至整个数组有序。

function shellSort(arr) {
  let gap = Math.floor(arr.length / 2); // 初始步长
  while (gap > 0) {
    for (let i = gap; i < arr.length; i++) {
      let temp = arr[i];
      let j = i;
      // 对子序列进行插入排序
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2); // 缩小步长
  }
  return arr;
}

特点：

• 时间复杂度：平均O(n^1.3)，比O(n²)好很多
• 空间复杂度：O(1)
• 不稳定排序

适用场景：中等规模的数据排序。

5. 归并排序 - 分而治之的经典算法

归并排序采用分治法的思想：将数组分成两半，分别排序，然后将两个有序数组合并成一个有序数组。

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 = [];
  while (left.length && right.length) {
    // 比较两个数组的第一个元素，取较小的放入结果
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }
  return result.concat(left, right); // 合并剩余元素
}

特点：

• 时间复杂度：始终O(n log n)
• 空间复杂度：O(n)(需要额外的存储空间)
• 稳定排序

适用场景：大规模数据排序，特别是需要稳定排序的情况。

6. 堆排序 - 基于二叉堆的排序

堆排序是一种基于**二叉堆(优先队列)**的排序算法。它首先构建一个最大堆，然后不断取出堆顶元素(最大值)放到数组末尾。

function heapSort(arr) {
  const n = arr.length;
  
  // 构建最大堆
  function heapify(i, heapSize) {
    let largest = i; // 初始化最大值为当前节点
    const left = 2 * i + 1; // 左子节点
    const right = 2 * i + 2; // 右子节点
    
    // 如果左子节点存在且大于当前最大值
    if (left < heapSize && arr[left] > arr[largest]) {
      largest = left;
    }
    
    // 如果右子节点存在且大于当前最大值
    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }
    
    // 如果最大值不是当前节点，交换并继续堆化
    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(largest, heapSize);
    }
  }
  
  // 构建最大堆(从最后一个非叶子节点开始)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(i, n);
  }
  
  // 逐个取出堆顶元素
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 将堆顶元素(最大值)与当前末尾交换
    heapify(0, i); // 对剩余元素重新堆化
  }
  
  return arr;
}

特点：

• 时间复杂度：始终O(n log n)
• 空间复杂度：O(1)
• 不稳定排序

适用场景：需要高效排序且内存有限的情况。

7. 快速排序 - 最常用的排序算法

快速排序也是一种分治法的排序算法。它选择一个"基准"元素，将数组分为两部分：小于基准的和大于基准的，然后递归地对这两部分进行排序。

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++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)]; // 递归排序并合并
}

更高效的实现(原地分区)：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right); // 获取分区点
    quickSort(arr, left, pivotIndex - 1); // 递归排序左半部分
    quickSort(arr, pivotIndex + 1, right); // 递归排序右半部分
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right]; // 选择最右边的元素作为基准
  let i = left; // i是小于基准的元素的边界
  
  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)(递归调用栈)
• 不稳定排序

适用场景：大规模数据排序，追求性能的情况。

8. 计数排序 - 非比较排序算法

计数排序是一种非比较排序算法，适用于整数排序。它的基本思想是：统计每个元素出现的次数，然后根据统计结果重建有序数组。

function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0); // 统计每个元素出现的次数
  for (let num of arr) {
    count[num]++;
  }
  
  const result = [];
  for (let i = 0; i <= maxVal; i++) {
    while (count[i]-- > 0) {
      result.push(i); // 根据统计结果重建数组
    }
  }
  
  return result;
}

特点：

• 时间复杂度：O(n + k)(k是数据的范围)
• 空间复杂度：O(k)
• 稳定排序(如果实现得当)

适用场景：数据是整数且范围不大的情况。

9. 桶排序 - 分配到多个桶中排序

桶排序将元素分散到多个"桶"中，每个桶内部进行排序，最后合并所有桶的结果。

function bucketSort(arr, bucketSize = 5) {
  if (arr.length <= 1) return arr;
  
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1; // 计算桶的数量
  const buckets = Array.from({ length: bucketCount }, () => []); // 创建桶
  
  // 将元素分配到各个桶中
  for (let num of arr) {
    const index = Math.floor((num - min) / bucketSize);
    buckets[index].push(num);
  }
  
  // 对每个桶进行排序并合并结果
  return buckets.flatMap(bucket => insertionSort(bucket)); // 这里使用了插入排序
}

特点：

• 时间复杂度：O(n + k)，最坏O(n²)(当所有元素都在一个桶中)
• 空间复杂度：O(n + k)
• 稳定排序(取决于桶内使用的排序算法)

适用场景：数据分布均匀的情况，特别是浮点数排序。

10. 基数排序 - 按位比较的排序

基数排序是一种非比较排序算法，它按照数字的位数从低位到高位依次排序。

function radixSort(arr) {
  const max = Math.max(...arr);
  let exp = 1; // 从个位开始
  
  while (Math.floor(max / exp) > 0) {
    countingByDigit(arr, exp); // 按当前位排序
    exp *= 10; // 移动到下一位
  }
  
  return arr;
}

function countingByDigit(arr, exp) {
  const output = new Array(arr.length).fill(0);
  const count = new Array(10).fill(0); // 0-9的数字
  
  // 统计当前位数字出现的次数
  for (let num of arr) {
    count[Math.floor(num / exp) % 10]++;
  }
  
  // 计算累计次数
  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]] = arr[i];
  }
  
  // 将排序结果复制回原数组
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

特点：

• 时间复杂度：O(nk)(k是最大数字的位数)
• 空间复杂度：O(n + k)
• 稳定排序

适用场景：非负整数排序，特别是位数不多的情况。

排序算法性能对比

总结

1. 简单排序：冒泡、选择、插入排序适合小规模数据或学习理解
2. 高效排序：归并、堆、快速排序适合大规模数据
3. 特殊排序：计数、桶、基数排序适合特定场景(整数、浮点数等)

在实际开发中，JavaScript的Array.prototype.sort()方法已经足够高效，它通常使用快速排序或归并排序的变体。但理解这些底层算法原理，能帮助我们更好地解决问题和优化代码。

希望这篇通俗易懂的排序算法指南对你有所帮助！

推荐更多阅读内容
掌握这些JavaScript技巧，让你的编码效率飙升！
JavaScript 字符串字符删除方法大揭秘
正向代理与反向代理：傻傻分不清楚
JavaScript分钟转时间格式（小时+分钟）的方法及应用
彻底理解 Object.entries() + map()：如何把对象转换成指定格式数组？
深入理解 window.open：用法、参数、兼容性与安全实践
彻底清除和禁用浏览器输入框历史记录的终极指南
JavaScript 开发中的高效技巧与基础知识解析