十大排序

本文最后更新于 2025年9月14日 上午

参考：
https://github.com/biaochenxuying/blog/issues/42
https://juejin.cn/post/6956624975600025613

排序有冒泡排序、插入排序、选择排序、归并排序等十种经典方法。分析一个排序算法，可以从执行效率、内存消耗、稳定性三方面入手。

稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。

排序算法，图源网络

冒泡排序

思路

  • 每次冒泡是对相邻的两个元素进行比较，看是否满足特定关系要求，若（不）满足就互换
  • 一次冒泡会让至少一个元素移动到它应在的位置，重复 n - 1 次就能完成 n 个数据的排序工作

特点

  • 优点：排序算法的基础，简单实用易于理解
  • 缺点：使用多个循环，比较次数多，效率较低

实现

普通：

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
function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
// 或者
function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      const n1 = arr[j];
      const n2 = arr[j + 1];
      if (n2 < n1) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

优化（某次冒泡操作已经没有数据交换，说明已经达到完全有序，不用再继续执行后续的冒泡操作）：

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

  for (let i = 0; i < len - 1; i++) {
    let hasChange = false;
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        hasChange = true;
      }
    }
    if (!hasChange) break;
  }
  return arr;
}

分析

  • 冒泡的过程中只涉及相邻数据的交换操作，只需要常量级的临时空间，所以空间复杂度为 O(1)，是一个原地排序算法
  • 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。
    为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等时不做交换，相同大小的数据在排序前后不会改变顺序。所以冒泡排序是稳定的排序算法。
  • 最佳情况：T(n) = O(n)，当数据已经是正序时。
    最差情况：T(n) = O(n2)，当数据是反序时。
    平均情况：T(n) = O(n2)。

选择排序

思路

  • 构建有序序列和未排序序列。认为第一个元素已经被排序，其余均为未排序序列的元素
  • 选择排序每次会从未排序序列中找到最小（大）的元素，将其放到已排序区间的开头（末尾）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 选择排序 */
function selectionSort(nums) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 外层循环：从第 i 个位置开始
    let minInd = i; // 假设当前位置是最小值
    let minVal = arr[i];
    for (let j = i + 1; j < len; j++) {
      // 内层循环：找后面是否有更小的值
      const curVal = arr[j];
      // 找到更小的值
      if (curVal < minVal) {
        minInd = j;
        minVal = curVal;
      }
    }
    // 交换，把最小值放到当前位置
    [arr[i], arr[minInd]] = [arr[minInd], arr[i]];
  }
  return arr;
}

分析

  • 选择排序空间复杂度为 O(1)，是一种原地排序算法
  • 选择排序每次都要找剩余未排序元素中的最小值并和前面的元素交换位置，这样破坏了稳定性。所以选择排序是一种不稳定的排序算法
  • 无论是正序还是逆序，都会遍历 n2 / 2 次来排序，所以，最佳、最差和平均的复杂度是一样的。
    最佳情况：T(n) = O(n2)。
    最差情况：T(n) = O(n2)。
    平均情况：T(n) = O(n2)。

插入排序

插入排序分为 直接插入排序 和优化后的 拆半插入排序 与 希尔排序，通常说的插入排序是指直接插入排序。

思路

  • 构建有序序列和未排序序列。认为第一个元素已经被排序，其余均为未排序序列的元素
  • 插入排序每次从未排序序列中取出一个元素，然后在有序序列中从后向前扫描，如果有序序列中的元素大于取出的元素，将该元素移到该元素的下一位置，直到找到相应位置并插入

实现

普通：

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
function insertSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let pivotVal = arr[i];
    let preIndex = i - 1;
    while (preIndex >= 0 && arr[preIndex] > pivotVal) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = pivotVal;
  }
  return arr;
}

function insertSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    // 外层循环：从第二个元素开始，依次插入前面有序序列
    const pivotVal = arr[i]; // 待插入的元素
    for (let j = i - 1; j >= 0; j--) {
      // 内层循环：从后往前找合适位置
      const curVal = arr[j];
      if (pivotVal < curVal) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 元素后移
      } else {
        break; // 这里 break，表示找到插入位置
      }
    }
  }
  return arr;
}

改进：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binaryInsertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    let low = 0,
      high = i - 1,
      current = arr[i];
    while (low <= high) {
      let m = (low + high) >> 1;
      if (arr[i] >= arr[m]) low = m + 1;
      else high = m - 1;
    }
    for (let j = i; j > low; j--) arr[j] = arr[j - 1];
    arr[low] = current;
  }
  return arr;
}

分析

  • 插入排序算法的运行并不需要额外的存储空间，空间复杂度是 O(1)，所以这是一个原地排序算法
  • 在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法
  • 最佳情况：T(n) = O(n)，当数据已经是正序时。
    最差情况：T(n) = O(n2)，当数据是反序时。
    平均情况：T(n) = O(n2)。

归并排序

思想

归并排序采用的是分治思想，就是分而治之：将一个大问题分解成小的子问题，小的子问题解决了，大问题也就解决了。排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。可以分为“划分”和“合并”两个阶段：

  • 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题
  • 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束

实现

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
const mergeSort = (arr) => {
  // 采用自上而下的递归方法
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  // length >> 1 和 Math.floor(len / 2) 等价
  const middle = Math.floor(len / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle); // 拆分为两个子数组
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const result = [];

  while (left.length && right.length) {
    // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }

  while (right.length) {
    result.push(right.shift());
  }

  return result;
};

分析

  • 归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
    尽管每次合并操作都需要申请额外的内存空间，但在合并完成后临时开辟的内存空间会被释放。在任意时刻，只有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。所以，归并排序不是原地排序算法。
  • merge 方法里面的 left[0] <= right[0] 保证了值相同的元素，在合并前后的先后顺序不变。归并排序是稳定的排序方法。
  • 从效率上看归并排序算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步，又每步都是一个普通的合并子数组过程，时间复杂度为 O(n)，故综合时间复杂度为 O(n log n)。
    最佳情况：T(n) = O(n log n)。
    最差情况：T(n) = O(n log n)。
    平均情况：T(n) = O(n log n)。

快速排序

思想

先找到一个基准点（一般是数组中部），然后数组被该基准点分为两部分，依次与该基准点数据比较。如果比它小，放左边；反之放右边。左右分别用一个空数组去存储比较后的数据。最后递归执行上述操作，直到数组长度小于等于 1。

特点

  • 优点：快速，常用，效率高，是处理大数据最快的算法之一
  • 缺点：需要另外声明两个数组，浪费了内存空间资源

实现

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
// 方法一
const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    const partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
};

const partition = (arr, left, right) => {
  //分区操作
  const pivot = left; //设定基准值（pivot）
  let index = pivot + 1;
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      [arr[i], arr[index]] = [arr[index], arr[i]];
      index++;
    }
  }
  [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]];
  return index - 1;
};

// 方法二
// 快速排序
function quickSort(arr) {
  const len = arr.length;
  if (len <= 1) {
    return arr;
  }
  const midIndex = Math.floor(len / 2);
  const valArr = arr.splice(midIndex, 1);
  const midIndexVal = valArr[0];
  const left = [];
  const right = [];
  // 此时 len != arr.length
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midIndexVal) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(midIndexVal, quickSort(right));
}

分析

  • 不需要很多额外的内存空间，所以快排是原地排序算法
  • 和选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此有可能打破原来值为相同元素之间的顺序。因此，快速排序并不稳定
  • 最佳情况：T(n) = O(n log n)。
    最差情况：T(n) = O(n2)。
    平均情况：T(n) = O(n log n)。

对比

快排和归并用的都是分治思想，递推公式和递归代码也非常相似，区别在于：

  • 归并排序的处理过程是由下而上的，先处理子问题，然后再合并。快排正好相反，它的处理过程是由上而下的，先分区，然后再处理子问题
  • 归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但它是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数可以实现原地排序，解决了归并排序占用太多内存的问题

希尔排序

思想

  • 构建有序序列和未排序序列。认为第一个元素已经被排序，其余均为未排序序列的元素
  • 先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序，等到整个序列中记录基本有序时，再对全体记录进行依次直接插入排序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function shellSort(arr) {
  const len = arr.length;
  let temp;
  let gap = 1;
  console.time("希尔排序耗时");
  while (gap < len / 3) {
    //动态定义间隔序列
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
      let j = i - gap;
      for (; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
      console.log("arr  :", arr);
    }
  }
  console.timeEnd("希尔排序耗时");
  return arr;
}

分析

  • 希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法
  • 单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但是在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化
  • 最佳情况：T(n) = O(n log n)。
    最差情况：T(n) = O(n log2 n)。
    平均情况：T(n) = O(n log2 n)。

堆排序

1

桶排序

1

计数排序

1

基数排序

1

计算机基础 > 算法
#算法
十大排序
https://xuekeven.github.io/2021/09/18/十大排序/
作者
Keven
发布于
2021年9月18日
更新于
2025年9月14日
许可协议