type
Post
status
Published
date
Mar 12, 2026
slug
summary
tags
刷题
category
技术分享
icon
password
这里写文章的前言：
一个简单的开头,简述这篇文章讨论的问题、目标、人物、背景是什么？并简述你给出的答案。
可以说说你的故事：阻碍、努力、结果成果，意外与转折。
对比
排序的稳定性（归并/冒泡/插入稳定，快排/堆排/选择不稳定）、时间复杂度、空间复杂度是面试必问的配套知识点。
稳定性：在排序过程中，值相等的元素经过排序后，依然保持它们在原始数组中的相对先后位置，这种排序算法就是稳定的，反之则不稳定。
排序算法 | 稳定性 | 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 核心备注（面试考点） |
快速排序 | 不稳定 | O(nlogn) | O(n2) | O(nlogn) | O(logn) | 面试最高频；最坏场景为有序数组，需选基准 |
归并排序 | 稳定 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 分治思想；合并有序数组是核心手写考点 |
堆排序 | 不稳定 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 原地排序；需理解堆化、最大堆构建逻辑 |
冒泡排序 | 稳定 | O(n) | O(n2) | O(n2) | O(1) | 优化点：标记交换，无交换则提前终止 |
选择排序 | 不稳定 | O(n2) | O(n2) | O(n2) | O(1) | 选最值交换；易理解但效率低，无最好优化 |
插入排序 | 稳定 | O(n) | O(n2) | O(n2) | O(1) | 适合近乎有序数组；局部有序思想 |
为什么快速排序是「原地排序」仍然有空间复杂度？ 快速排序的空间消耗核心是递归调用栈，平均O(logn)、最坏O(n)，这是分治递归的必然结果；
除归并排序外，其余 5 种排序算法均为「原地排序」
原地排序的 O (nlogn) 算法？ 快速排序和堆排序。（他们俩都不稳定）
是否存在 O (nlogn)、原地且稳定的排序？ 理论上存在（如 Block Sort），但非经典算法，实际开发 / 刷题中不用。
Python里.sort()等是什么排序？，业界一般用哪个？ Timsort（蒂姆排序）是工业界最主流、最万金油的排序算法 —— 它是 Pythonlist.sort()/sorted()、JavaArrays.sort()（针对对象数组）、Android、Chrome 等核心场景的默认排序实现。
进阶排序 O(nlogn)
1. 快速排序（面试最高频，分治思想）
核心特点：平均时间复杂度O(nlogn)，「原地」排序，非稳定；面试必问“基准值选择”“分区逻辑”。
2. 归并排序（分治+稳定，面试常考）
核心特点：稳定排序，时间复杂度O(nlogn)，需要「额外空间」；核心是“分-合”两步。
3. 堆排序（基于堆结构，关联优先队列）
核心特点：O(nlogn)，「原地」排序，非稳定；面试常和
heapq结合考察。基础排序 O(n²)
4. 冒泡排序（基础，理解交换思想）
核心特点：O(n²)，稳定排序，原地操作；面试常问“如何优化（提前终止）”。
5. 选择排序（基础，选择最值思想）
核心特点：O(n²)，非稳定，原地排序；核心是“找最小值放到已排序区末尾”。
6. 插入排序（基础，局部有序思想）
核心特点：O(n²)，稳定排序，原地操作；适合近乎有序的数组，面试常问“优化（希尔排序）”。
扩展阅读
经典排序为何成很少在工业界直接应用？
排序算法 | 工业界不适用的核心原因 |
快速排序 | 不稳定，最坏 O (n²)（极端数据易超时），业务场景易踩坑 |
归并排序 | 非原地（空间 O (n)），内存开销大，不适合大数据量 |
堆排序 | 不稳定，对 CPU 缓存不友好（实际运行效率低），仅适合特定场景（如优先队列） |
冒泡 / 插入 / 选择 | O (n²) 时间复杂度，仅小数据量可用，无工业级价值 |
Timsort 的工业级完整实现难度极高，远超出普通开发者（甚至面试）的要求；但理解其核心思路很简单，完全不需要手写完整版本。
- Author:YelloooBlue
- URL:https://tangly1024.com/article/321e32f0-1b7f-8059-8332-c2560b01d2a4
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
