排序算法 时间复杂度、空间复杂度

一、时间复杂度

1. 什么是时间复杂度

• 记为大O，是衡量算法运行效率的重要指标，描述了算法运行所需时间是如何随着输入规模（通常用n来表示）变化的（一般）。也可以说用来表示算法语句总的执行次数随n的增长趋势。

2. 常见时间复杂度的分类

时间复杂度	描述	例子
O(1)	常数时间：与输入大小无关	访问数组中的某元素
O(log n)	对数时间：规模缩小一半	二分查找
O(n)	线性时间：与输入成正比	遍历数组
O(n log n)	线性对数时间	快速排序、归并排序
O(n^2)	二次方时间：嵌套循环	冒泡排序、插入排序
O(2^n)	指数时间	未优化递归解决斐波那契数列
O(n!)	阶乘时间	解决全排列问题

3. 时间复杂度的分析方法

• 确定基本操作的时间复杂度
• 分析循环结构或递归共识
• 省略低阶项和常数，仅保留增长最快的项

---

二、空间复杂度

1. 什么是空间复杂度

• 同样使用大O来表示，用来衡量算法在运行过程中所需的存储空间随输入规模(n)的变化。

2. 空间复杂度的分类

空间复杂度	描述	示例算法
O(1)	常数空间：不需要额外空间	原地排序算法（如冒泡排序）
O(log n)	对数空间：递归深度相关	二分查找递归实现
O(n)	线性空间：与输入大小相关	动态规划、哈希表
O(n^2)	二次空间：二维矩阵相关	矩阵操作、图的存储

3. 空间复杂度的分析方法

• 统计变量：分析算法中引入了多少额外变量。
  • 普通变量占用 O(1) 空间。
  • 数组或列表根据其大小占用 O(n) 空间。
• 递归深度：递归算法会消耗额外的栈空间，其大小由递归深度决定。
  • 递归调用栈的深度为 ( d )，每次调用需要固定大小的空间，则总空间复杂度为 O(d) 。
• 动态数据结构：动态创建的结构（如链表、树、哈希表）占用的空间与输入规模相关。

4. 时间复杂度和空间复杂度的权衡：

• 有些算法可以通过增加空间来换取时间效率（如动态规划的备忘录法）。
• 也可以通过减少空间来牺牲时间（如递归转循环）。

---

三、排序算法的比较

1. 基于比较的排序

• 依赖元素之间的比较操作。
• 包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等。

2. 非比较排序

• 不直接比较元素大小，而是利用元素的特性。
• 包括计数排序、桶排序和基数排序。

3. 各排序算法的比较

排序算法	时间复杂度（最坏/平均/最好）	空间复杂度	稳定性	特点与适用场景
冒泡排序	O(n^2) / O(n^2) / O(n)	O(1)	稳定	简单实现，适合小规模数据或数据接近有序的场景
选择排序	O(n^2)	O(1)	不稳定	简单但效率低，不适合大数据
插入排序	O(n^2) / O(n^2) / O(n)	O(1)	稳定	适合少量数据或几乎有序的数组
归并排序	O(n log n)	O(n)	稳定	适合大数据、需要稳定性的场景
快速排序	O(n^2) / O(n log n) / O(n log n)	O( log n)	不稳定	高效通用的排序算法，适合大规模数据
堆排序	O(n log n)	O(1)	不稳定	用于堆结构的场景，内存使用较少
计数排序	O(n + k)	O(n + k)	稳定	适用于数据范围较小且整数数据的场景
桶排序	O(n + k)	O(n + k)	稳定	适合数据均匀分布的场景
基数排序	O(n * k)	O(n + k)	稳定	适合多位数值或字符串的排序

• 稳定性：当值相等时，排序后是否保持原顺序。

四、各算法介绍

1. 冒泡排序

• 原理：两两比较相邻元素，将较大的元素逐步“冒泡”到数组末尾。
• 特点：简单易懂，但性能较低。
• 适用场景：小数据量或数据接近有序时。

2. 选择排序

• 原理：每次从未排序部分选择最小（或最大）的元素，放到已排序部分末尾。
• 特点：实现简单，但多次交换导致效率低。
• 适用场景：数据量小，稳定性不要求高。

3. 插入排序

• 原理：将未排序元素逐一插入到已排序部分的适当位置。
• 特点：对几乎有序的数据效果较好。
• 适用场景：小规模数据、接近有序数据。

4. 快速排序

• 原理：选定一个基准值，将数组划分为小于和大于基准值的两部分，递归排序。
• 特点：平均性能优越，但最坏情况下效率低（如有序数组）。
• 适用场景：大规模数据，效率高要求。

5. 归并排序

• 原理：将数组递归分成两部分，分别排序后合并。
• 特点：稳定且效率高，但需要额外空间。
• 适用场景：需要稳定性，且内存足够的场景。

总结与选择建议

1. 数据量小或几乎有序：

   • 使用 插入排序 或 冒泡排序。

2. 大数据量，追求效率：

   • 快速排序：时间效率高，适用范围广。
   • 归并排序：稳定，适合外部排序。

3. 内存有限：

   • 堆排序：占用空间小，但不稳定。

4. 整数或范围较小数据（外部排序）：

   • 计数排序、桶排序、基数排序。

5. 不稳定的排序：

   • 选择排序、快速排序、堆排序

6. 时间复杂度稳定为O( n log n )的排序

   • 归并排序、堆排序

7. 速记方法：

   • 平均时间复杂度O(n^2)，较为低效，但空间复杂度为O(1)的排序算法：
     • 冒泡：稳定
     • 选择：不稳定
     • 插入：稳定
   • 平均时间复杂度O(n log n)，较为高效的算法：
     • 归并：稳定，空间复杂度为O(n)
     • 快速：不稳定，空间复杂度为O(log n)，时间复杂度最坏时为O(n^2)
     • 堆：不稳定，空间复杂度为O(1)

原文地址：https://blog.csdn.net/wechatonly/article/details/143954468

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！