排序算法

排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

如下图所示，排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则。

[

评价维度

运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。

就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

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

稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失：

# 输入数据是按照姓名排序好的
# (name, age)
  ('A', 19)
  ('B', 18)
  ('C', 21)
  ('D', 19)
  ('E', 23)

# 假设使用非稳定排序算法按年龄排序列表，
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变，
# 输入数据按姓名排序的性质丢失
  ('B', 18)
  ('D', 19)
  ('A', 19)
  ('C', 21)
  ('E', 23)

自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。

是否基于比较：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 O(nlog⁡n) 。而非比较排序不使用比较运算符，时间复杂度可达 O(n) ，但其通用性相对较差。

排序算法对比表

排序算法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性	适用场景
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	是	小数据量，基本有序
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否	小数据量
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	是	小数据量，基本有序
希尔排序	$\text{O(n^\&\#123;1.3\&\#125;)}$	$O(n^2)$	$O(n)$	$O(1)$	否	中小数据量
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	是	稳定排序，大数据量
快速排序	$O(n\log n)$	$O(n^2)$	$O(n\log n)$	$O(\log n)$	否	一般场景，大数据量
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	否	对空间要求高，大数据量
基数排序	$O(d(n+k))$	$O(d(n+k))$	$O(d(n+k))$	$O(n+k)$	是	数字/字符串，范围已知
桶排序	$O(n+k)$	$O(n^2)$	$O(n+k)$	$O(n+k)$	是	数据均匀分布，范围已知

---

总结与选择建议

1. 数据量较小：
   • 使用 插入排序 或 冒泡排序，实现简单，性能尚可。
2. 需要稳定性：
   • 使用 归并排序 或 基数排序。
3. 需要高效排序：
   • 使用 快速排序 或 堆排序，适合大规模数据。
4. 特定场景：
   • 数据范围较小时，可选用 基数排序 或 桶排序。
   • 数据基本有序时，插入排序 更高效。

各种排序特性

1. 冒泡排序（Bubble Sort）

基本原理 逐步比较相邻的元素，将较大的元素逐步移动到数组末尾。

特性

• 时间复杂度:
  • 最好情况: O(n)（已排序，且无需交换）
  • 最坏情况: $O(n^2)$
  • 平均情况: $O(n^2)$
• 空间复杂度: O(1)（原地排序，无需额外空间）
• 是否稳定: 是（相等元素的相对位置不会改变）
• 适用场景: 数据量小、近似有序。

优缺点

• 优点: 简单易实现。
• 缺点: 效率低，特别是数据量大的情况下。

---

2. 选择排序（Selection Sort）

基本原理 每次选择未排序部分的最小（或最大）元素，放到已排序部分的末尾。

特性

• 时间复杂度:
  • 最好情况: $O(n^2)$
  • 最坏情况: $O(n^2)$
  • 平均情况: $O(n^2)$
• 空间复杂度: O(1)
• 是否稳定: 否（可能打破相等元素的顺序）
• 适用场景: 数据量小，对稳定性无要求。

优缺点

• 优点: 不依赖初始数据状态，交换次数较少。
• 缺点: 时间复杂度高，效率低。

---

3. 插入排序（Insertion Sort）

基本原理 将每个元素插入到前面已排序部分的适当位置。

特性

• 时间复杂度:
  • 最好情况: $O(n)$（已排序）
  • 最坏情况:$O(n^2)$
  • 平均情况: $O(n^2)$
• 空间复杂度: O(1)
• 是否稳定: 是
• 适用场景: 数据量小或数据基本有序。

优缺点

• 优点: 简单高效，对小规模和基本有序数据表现良好。
• 缺点: 对大规模、无序数据效率低。

---

4. 希尔排序（Shell Sort）

基本原理 通过分组和缩小增量的插入排序，提高效率。

特性

• 时间复杂度: $\text{O(n^\&\#123;1.3\&\#125; sim n^2)}$（取决于增量序列）
• 空间复杂度: O(1)
• 是否稳定: 否
• 适用场景: 中小规模数据排序。

优缺点

• 优点: 相比插入排序效率高。
• 缺点: 对稳定性和大规模数据表现不佳。

---

5. 归并排序（Merge Sort）

基本原理 采用分治思想，将数组递归拆分成两部分，排序后合并。

特性

• 时间复杂度:$O(n\log n)$
• 空间复杂度: $O(n)$(需要辅助数组）
• 是否稳定: 是
• 适用场景: 需要稳定排序且数据量大。

优缺点

• 优点: 时间复杂度稳定，适用于大规模数据。
• 缺点: 占用额外空间，递归调用耗费栈空间。

---

6. 快速排序（Quick Sort）

基本原理 选择一个基准值，将数据分为小于和大于基准值的两部分，递归排序。

特性

• 时间复杂度:
  • 最好情况: $O(n\log n)$
  • 最坏情况: $O(n^2)$（数据完全有序或逆序）
  • 平均情况: $O(n\log n)$
• 空间复杂度: $O(logn)$（递归栈）
• 是否稳定: 否
• 适用场景: 一般场景，适合大规模数据。

优缺点

• 优点: 时间复杂度较低，效率高。
• 缺点: 对部分数据分布不均的情况性能较差。

---

7. 堆排序（Heap Sort）

基本原理 利用堆（完全二叉树）结构特性，构建最大（或最小）堆，逐步取出堆顶元素。

特性

• 时间复杂度: $O(nlogn)$
• 空间复杂度: $O(1)$
• 是否稳定: 否
• 适用场景: 需要较低的空间复杂度。

$\mathrm{优}\mathrm{缺}\mathrm{点}$

• 优点: 时间复杂度稳定，不需要额外空间。
• 缺点: 实现较复杂，不稳定。

---

8. 基数排序（Radix Sort）

基本原理 按位进行多次排序，从低位到高位依次排序。

特性

• 时间复杂度: $O(d\cdot (n+k))$，其中 d 是位数，k 是基数。
• 空间复杂度: $O(n+k)$
• 是否稳定: 是
• 适用场景: 数字或字符串排序，数据范围有限。

优缺点

• 优点: 对某些特定数据类型非常高效（如数字）。
• 缺点: 需要额外空间，对非整数数据不适用。

---

9. 桶排序（Bucket Sort）

基本原理 将数据划分到多个桶中，分别对桶内数据排序，最后合并。

特性

• 时间复杂度: $O(n+k)$（k 是桶的数量）
• 空间复杂度: $O(n+k)$
• 是否稳定: 是（取决于桶内排序方式）
• 适用场景: 数据均匀分布，且范围已知。

优缺点

• 优点: 对数据分布要求高时表现优异。
• 缺点: 对数据不均匀分布不适用，占用较多内存。

10. 计数排序（Counting Sort）

基本原理
统计每个元素出现的次数，将统计结果存储在辅助数组中，然后根据统计结果将元素按顺序输出到目标数组中。

特性

• 时间复杂度:$O(n+k)$，其中 n 是输入数组的大小，k 是数据范围（最大值与最小值的差）。
• 空间复杂度: O(k)，需要额外的计数数组存储数据范围内的统计信息。
• 是否稳定: 是（如果在统计排序时保留原始相对顺序）。
• 适用场景: 数据范围较小的整数型数据（如年龄、成绩等）。

---

优缺点

• 优点:
  • 时间复杂度为线性级别，效率高。
  • 非比较排序，不会受输入数据规模影响。
• 缺点:
  • 需要额外的计数数组，数据范围过大时空间消耗较多。
  • 仅适用于整数数据，不适合浮点数或数据范围未知的情况。