常见排序算法

答：

1.

补充

补充：常见排序算法速览：

  • 冒泡排序：O(n²)，稳定，通过相邻元素两两比较交换实现。
  • 选择排序：O(n²)，不稳定，每轮选最小/最大放到边界。
  • 插入排序：O(n²)，稳定，对近乎有序的数据性能好（最佳 O(n)）。
  • 希尔排序：插入排序的改进版，按"间隔"分组排序，逐步缩小间隔，时间约 O(n log² n)。
  • 归并排序：O(n log n)，稳定，分治思想，递归实现，需要 O(n) 额外空间。
  • 快速排序：O(n log n) 平均 / O(n²) 最坏，不稳定，分治 + 基准划分，原地排序（O(log n) 栈空间）。
  • 堆排序：O(n log n)，不稳定，利用最大堆/最小堆原地排序。
  • 计数排序 / 桶排序 / 基数排序：O(n + k) 级别的线性排序，但有适用范围（如数据范围有限或可分桶）。

实际工程中 V8 的 Array.prototype.sort 在长度较小时使用插入排序，规模较大时使用 TimSort（归并排序变种）。

来源整理自：我的有道云笔记