常用的排序算法

常用的排序算法

Wreckloud_雲之残骸 Lv4
  2025-04-21 21:53:32 2025-04-21 21:53:32 创建   2025-04-21 21:58:44 2025-04-21 21:58:44 更新  1.9k 字  8 分钟  

冒泡排序 (Bubble Sort)

时间复杂度: O(n²) - 最坏、平均情况
空间复杂度: O(1) - 原地排序
稳定性: 稳定

工作原理:
重复遍历数组，比较相邻元素并交换位置
每轮遍历将当前最大元素”冒泡”到末尾
下一轮遍历长度减少 1(已排序部分)

@param {Array} arr - 需要排序的数组
@return {Array} - 排序后的数组(原地修改)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function bubbleSort(arr) {
  const len = arr.length;

  // 外层循环控制排序轮数
  for (let i = 0; i < len - 1; i++) {
    // 优化标志: 如果一轮中没有交换，则数组已排序
    let swapped = false;

    // 内层循环比较相邻元素
    // 注意 j < len - 1 - i: 每轮后最大的i个元素已确定
    for (let j = 0; j < len - 1 - i; j++) {
      // 如果当前元素大于下一个元素，交换它们
      if (arr[j] > arr[j + 1]) {
        // ES6解构赋值语法完成交换
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // 如果本轮未发生交换，数组已排序，提前退出
    if (!swapped) break;
  }

  return arr;
}

插入排序 (Insertion Sort)

时间复杂度: O(n²) - 最坏、平均情况; O(n) - 最好情况(已排序)
空间复杂度: O(1) - 原地排序
稳定性: 稳定

工作原理:
将数组分为已排序和未排序两部分
初始时已排序部分只有第一个元素
每次从未排序部分取出一个元素，插入到已排序部分的正确位置
像整理扑克牌一样逐步构建有序数组

@param {Array} arr - 需要排序的数组
@return {Array} - 排序后的数组(原地修改)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function insertionSort(arr) {
  const len = arr.length;

  // 从第二个元素开始，第一个元素视为已排序
  for (let i = 1; i < len; i++) {
    // 保存当前要插入的元素
    const 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;
}

快速排序 (Quick Sort)

时间复杂度: O(n log n) - 平均情况; O(n²) - 最坏情况
空间复杂度: O(log n) - 递归调用栈
稳定性: 不稳定

选择一个”基准”元素(pivot)
将小于基准的元素放左边，大于基准的放右边
递归地对左右两个子数组进行快速排序
分治法的典型应用

@param {Array} arr - 需要排序的数组
@param {number} [left=0] - 起始索引
@param {number} [right=arr.length-1] - 结束索引
@return {Array} - 排序后的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 递归终止条件: 子数组长度为1或更小
  if (left >= right) {
    return arr;
  }

  // 获取基准元素的最终位置
  const pivotIndex = partition(arr, left, right);

  // 递归排序基准左侧子数组
  quickSort(arr, left, pivotIndex - 1);
  // 递归排序基准右侧子数组
  quickSort(arr, pivotIndex + 1, right);

  return arr;
}

/**
 * 分区操作: 将数组分为小于和大于基准元素的两部分
 *
 * @param {Array} arr - 需要分区的数组
 * @param {number} left - 起始索引
 * @param {number} right - 结束索引
 * @return {number} - 基准元素的最终位置
 */
function partition(arr, left, right) {
  // 选择最右元素作为基准
  const pivot = arr[right];

  // i指向小于基准区域的最后一个元素
  let i = left - 1;

  // j遍历数组元素
  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;
}

归并排序 (Merge Sort)

时间复杂度: O(n log n) - 所有情况
空间复杂度: O(n) - 需要额外空间存储合并结果
稳定性: 稳定

分治法: 将数组分成两半，递归排序
将排序后的两半合并为一个有序数组
不断分割直到子数组长度为 1(天然有序)

@param {Array} arr - 需要排序的数组
@return {Array} - 排序后的新数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function mergeSort(arr) {
  const len = arr.length;

  // 递归终止条件: 数组长度为1时已排序
  if (len <= 1) {
    return arr;
  }

  // 将数组分为两半
  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // 递归排序两个子数组
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // 合并两个有序数组
  return merge(sortedLeft, sortedRight);
}

/**
 * 合并两个有序数组
 *
 * @param {Array} left - 第一个有序数组
 * @param {Array} right - 第二个有序数组
 * @return {Array} - 合并后的有序数组
 */
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 比较两个数组的元素，按序放入结果数组
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 将剩余元素添加到结果中
  // (两个数组中只有一个会有剩余元素)
  return result
    .concat(left.slice(leftIndex))
    .concat(right.slice(rightIndex));
}

计数排序 (Count Sort) - 适用于整数范围较小的场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 计数排序
 * 时间复杂度: O(n + k) - n是数组长度，k是整数范围
 * 空间复杂度: O(k) - 需要计数数组
 * 稳定性: 稳定(如果实现正确)
 *
 * 工作原理:
 * - 统计每个整数出现的次数
 * - 根据统计结果重建有序数组
 * - 非比较排序，适用于有限范围整数
 *
 * @param {Array<number>} arr - 需要排序的整数数组
 * @return {Array<number>} - 排序后的新数组
 */
function countSort(arr) {
  if (arr.length <= 1) return [...arr];

  // 找出数组中的最大值和最小值
  let max = arr[0];
  let min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
    if (arr[i] < min) min = arr[i];
  }

  // 计算计数数组的大小，偏移量为min
  const range = max - min + 1;
  const counts = new Array(range).fill(0);

  // 统计每个元素出现的次数
  for (let i = 0; i < arr.length; i++) {
    counts[arr[i] - min]++;
  }

  // 根据计数重建排序后的数组
  const result = [];
  for (let i = 0; i < range; i++) {
    // 将每个元素按照出现次数添加到结果数组
    while (counts[i] > 0) {
      result.push(i + min);
      counts[i]--;
    }
  }

  return result;
}

排序算法比较表

排序算法 时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 稳定性 特点
冒泡排序 O(n²) O(n) O(n²) O(1) 稳定 简单，适合小数据集
插入排序 O(n²) O(n) O(n²) O(1) 稳定 对近乎有序数据高效
快速排序 O(n log n) O(n log n) O(n²) O(log n) 不稳定 实际应用最广泛
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定 性能稳定但需额外空间
计数排序 O(n + k) O(n + k) O(n + k) O(k) 稳定 适用于整数范围较小情况

JavaScript 的 sort()方法在不同浏览器中实现方式不同，但大多采用这些算法的混合：

  • V8 引擎(Chrome/Node.js):  对于小数组（长度<10）使用插入排序，大数组使用快速排序的变种——TimSort（结合了归并排序和插入排序）
  • SpiderMonkey(Firefox): 使用归并排序
  • JavaScriptCore(Safari): 使用混合排序算法
  • 标题: 常用的排序算法
  • 作者: Wreckloud_雲之残骸
  • 创建于 : 2025-04-21 21:53:32
  • 更新于 : 2025-04-21 21:58:44
  • 链接: https://www.wreckloud.com/2025/04/21/猎识印记-领域/算法/常用的排序算法/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
常用的排序算法
  1. 冒泡排序 (Bubble Sort)
  2. 插入排序 (Insertion Sort)
  3. 快速排序 (Quick Sort)
  4. 归并排序 (Merge Sort)
  5. 计数排序 (Count Sort) - 适用于整数范围较小的场景
  6. 排序算法比较表