Skip to main content

排序算法

以下是JavaScript中常用排序算法的汇总，包含核心思路和代码实现，按“比较类排序”和“非比较类排序”分类，附时间复杂度说明：

一、比较类排序（通过比较元素大小排序）​

1. 冒泡排序（Bubble Sort）​

  • 核心思路：重复遍历数组，每次比较相邻元素，顺序错误则交换。每轮将最大元素“浮”到末尾，如同气泡上浮。
  • 代码实现：
function bubbleSort(arr) {
  const len = arr.length;
  // 外层循环控制轮数（最多n-1轮）
  for (let i = 0; i < len - 1; i++) {
    let swapped = false; // 优化：若本轮无交换，说明已排序
    // 内层循环比较相邻元素（忽略已排好的末尾i个元素）
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 交换元素
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 提前退出
  }
  return arr;
}
  • 时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序数组）。

2. 选择排序（Selection Sort）​

  • 核心思路：将数组分为“已排序区”和“未排序区”，每次从“未排序区”选最小元素，放到“已排序区”末尾。
  • 代码实现：
function selectionSort(arr) {
  const len = arr.length;
  // 外层循环控制已排序区长度（最多n-1次）
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i; // 记录未排序区最小元素索引
    // 内层循环找未排序区的最小值
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换最小元素到已排序区末尾
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}
  • 时间复杂度：O(n²)（所有情况）。

3. 插入排序（Insertion Sort）​

  • 核心思路：类似整理扑克牌，将元素逐个插入“已排序区”的正确位置（左侧有序，右侧待排序）。
  • 代码实现：
function insertionSort(arr) {
  const len = arr.length;
  // 从第2个元素开始（第一个元素默认有序）
  for (let i = 1; i < len; i++) {
    const temp = arr[i]; // 待插入元素
    let j = i - 1; // 已排序区末尾索引
    // 从后往前比较，找到插入位置
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j]; // 元素后移
      j--;
    }
    arr[j + 1] = temp; // 插入元素
  }
  return arr;
}
  • 时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序数组）。

4. 希尔排序（Shell Sort）​

  • 核心思路：插入排序的改进版，按“步长”分组，每组执行插入排序，逐步减小步长至1，最终完成排序。
  • 代码实现：
function shellSort(arr) {
  const len = arr.length;
  // 初始步长为数组长度的一半，逐步减半
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 按步长分组，对每组执行插入排序
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let j = i;
      // 组内元素比较（步长为gap）
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}
  • 时间复杂度：O(n¹.³)（平均），O(n²)（最坏）。

5. 归并排序（Merge Sort）​

  • 核心思路：分治法，将数组二分至单个元素，再合并两个有序子数组，递归完成整体排序。
  • 代码实现：
// 合并两个有序数组
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), right.slice(j));
}

// 归并排序主函数
function mergeSort(arr) {
  const len = arr.length;
  if (len <= 1) return arr; // 递归终止条件（单个元素有序）
  // 二分数组
  const mid = Math.floor(len / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  // 合并有序子数组
  return merge(left, right);
}
  • 时间复杂度：O(n log n)（所有情况）；空间复杂度O(n)。

6. 快速排序（Quick Sort）​

  • 核心思路：分治法，选“基准”元素，将数组分为“小于基准”和“大于基准”两部分，递归排序子数组。
  • 代码实现：
// 分区操作：返回基准元素的最终位置
function partition(arr, left, right) {
  const pivot = arr[right]; // 选最右侧元素为基准
  let i = left - 1; // 记录小于基准区域的边界
  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换到小于基准区域
    }
  }
  // 将基准元素放到最终位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1; // 返回基准索引
}

// 快速排序主函数
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;
}
  • 时间复杂度：O(n log n)（平均），O(n²)（最坏，如已排序数组选尾元素为基准）。

7. 堆排序（Heap Sort）​

  • 核心思路：利用“大顶堆”特性（父节点≥子节点），每次提取堆顶最大元素，调整剩余元素为新堆，重复至排序完成。
  • 代码实现：
// 调整堆（确保父节点≥子节点）
function heapify(arr, len, i) {
  let largest = i; // 初始化最大值为父节点
  const left = 2 * i + 1; // 左子节点索引
  const right = 2 * i + 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]];
    heapify(arr, len, largest);
  }
}

// 堆排序主函数
function heapSort(arr) {
  const len = arr.length;
  // 构建大顶堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(arr, len, i);
  }
  // 提取堆顶元素并调整堆
  for (let i = len - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 堆顶（最大）放末尾
    heapify(arr, i, 0); // 调整剩余元素为大顶堆
  }
  return arr;
}
  • 时间复杂度：O(n log n)（所有情况）。

二、非比较类排序（不依赖元素大小比较）​

8. 计数排序（Counting Sort）​

  • 核心思路：适合整数排序，通过统计每个元素的出现次数，直接计算其在结果中的位置。
  • 代码实现：
function countingSort(arr) {
  if (arr.length === 0) return arr;
  // 确定元素范围（min和max）
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  // 计数数组（统计每个元素出现次数）
  const count = new Array(range).fill(0);
  // 结果数组
  const result = new Array(arr.length);
  
  // 统计次数
  for (const num of arr) {
    count[num - min]++;
  }
  
  // 转换为前缀和（表示元素在结果中的位置）
  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }
  
  // 反向遍历原数组，放置元素到结果（保证稳定性）
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    result[count[num - min] - 1] = num;
    count[num - min]--;
  }
  
  return result;
}
  • 时间复杂度：O(n + k)（n为元素数，k为数值范围）；适合范围小的整数。

9. 桶排序（Bucket Sort）​

  • 核心思路：将元素分到多个“桶”中，每个桶内部排序（如用插入排序），最后合并所有桶。
  • 代码实现：
function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;
  // 确定桶的范围
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  // 计算桶数量
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  // 初始化桶（二维数组）
  const buckets = new Array(bucketCount).fill(0).map(() => []);
  
  // 将元素分配到桶中
  for (const num of arr) {
    const index = Math.floor((num - min) / bucketSize);
    buckets[index].push(num);
  }
  
  // 每个桶内部排序，再合并结果
  const result = [];
  for (const bucket of buckets) {
    if (bucket.length > 0) {
      insertionSort(bucket); // 桶内用插入排序
      result.push(...bucket);
    }
  }
  
  return result;
}
  • 时间复杂度：O(n + k)（平均，k为桶数）；适合元素均匀分布的场景。

10. 基数排序（Radix Sort）​

  • 核心思路：按“位数”从低到高排序，每轮按当前位用计数排序（或桶排序）处理。
  • 代码实现：
// 获取数字的第d位（从0开始，0为个位）
function getDigit(num, d) {
  return Math.floor(Math.abs(num) / Math.pow(10, d)) % 10;
}

// 计算最大数字的位数
function getMaxDigits(arr) {
  const max = Math.max(...arr.map(num => Math.abs(num)));
  return max === 0 ? 1 : Math.floor(Math.log10(max)) + 1;
}

// 基数排序主函数
function radixSort(arr) {
  if (arr.length === 0) return arr;
  const maxDigits = getMaxDigits(arr);
  
  // 按每位排序（从个位到最高位）
  for (let d = 0; d < maxDigits; d++) {
    // 创建10个桶（0-9）
    const buckets = new Array(10).fill(0).map(() => []);
    // 分配元素到对应桶
    for (const num of arr) {
      const digit = getDigit(num, d);
      buckets[digit].push(num);
    }
    // 合并桶，更新数组
    arr = [].concat(...buckets);
  }
  
  return arr;
}
  • 时间复杂度：O(n * k)（n为元素数，k为最大位数）；适合整数或可转换为位数的类型。

总结​

算法时间复杂度（平均）稳定性适用场景
冒泡排序O(n²)稳定小规模数据
选择排序O(n²)不稳定小规模数据，交换成本高时
插入排序O(n²)稳定近乎有序数据，小规模数据
希尔排序O(n¹.³)不稳定中大规模数据
归并排序O(n log n)稳定大规模数据，需稳定性
快速排序O(n log n)不稳定大规模数据，平均效率高
堆排序O(n log n)不稳定大规模数据，内存有限时
计数排序O(n + k)稳定整数，数值范围小
桶排序O(n + k)稳定均匀分布的数据
基数排序O(n * k)稳定整数或固定位数数据

实际开发中，可根据数据规模、分布特性和稳定性需求选择合适算法（如前端常用快速排序或内置的Array.sort()，其底层通常为混合排序算法）。