type
status
date
slug
summary
tags
category
icon
password
🧭 一、排序算法总体分类
分类 | 算法名称 | 时间复杂度 | 空间复杂度 | 稳定性 | 特点 |
基础排序 | 冒泡排序、选择排序、插入排序 | O(n²) | O(1) | 冒泡、插入稳定 | 实现简单 |
高级排序（基于分治） | 归并排序、快速排序 | O(n log n) | O(n) / O(log n) | 归并稳定 | 常用高效算法 |
线性排序（非比较型） | 计数排序、桶排序、基数排序 | O(n + k) | O(n + k) | 稳定 | 适用于整数或范围有限的键值 |
改进与混合算法 | 希尔排序、堆排序、TimSort（Python 内置） | O(n log n) | O(1)~O(n) | 堆不稳定 | 综合性能强 |
🧩 二、常见排序算法详解
1. 冒泡排序（Bubble Sort） — 基础入门
- 思想：相邻元素两两比较，大的往后“冒泡”。
思想就是每次确定一个数，放置到最后一位
第一趟确定最后一位，第二趟确定倒数第二位，......那么我们这样只需要确定（len-1）次即可
- 时间复杂度：O(n²)
- 稳定性：稳定
2. 选择排序（Selection Sort）
- 思想：每次从未排序部分选择最小的放到前面。
- 时间复杂度：O(n²)
- 稳定性：不稳定
3. 插入排序（Insertion Sort）
- 思想：每次将一个元素插入到已排序序列的合适位置。
- 时间复杂度：O(n²)，但在“几乎有序”数据中性能极佳。
- 稳定性：稳定
4. 希尔排序（Shell Sort）
- 思想：对间隔为 gap 的元素进行插入排序，逐步缩小 gap。
普通插入排序在数据“逆序”时效率很低，因为一次只能移动一格。因此对这种一次一次移动来进行优化。希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
- 时间复杂度：O(n log n) ~ O(n²)
- 稳定性：不稳定
5. 归并排序（Merge Sort） — 典型分治算法
- 思想：递归地将数组分为两半，排序后合并。
- 时间复杂度：O(n log n)
- 稳定性：稳定
6. 快速排序（Quick Sort）
- 思想：选取基准（pivot），将小于 pivot 的放左边，大于的放右边，递归处理。
- 时间复杂度：O(n log n)，最坏 O(n²)
- 稳定性：不稳定
7. 堆排序（Heap Sort）
- 思想：利用堆结构（最大堆）选出最大值并放末尾。
- 时间复杂度：O(n log n)
- 稳定性：不稳定
8. 计数排序（Counting Sort）
- 思想：统计每个数出现的次数，按次数输出。
- 时间复杂度：O(n + k)
- 稳定性：稳定
9. 桶排序（Bucket Sort）
- 思想：将数据分配到若干桶中，对每个桶单独排序后合并。
- 适用：数据分布均匀的浮点数。
10. 基数排序（Radix Sort）
- 思想：按个位、十位、百位…依次排序（低位优先法）。
- 时间复杂度：O(nk)
- 稳定性：稳定
🐍 三、Python 内置排序算法 — TimSort
- Python 的
sorted()和list.sort()使用 TimSort，是归并 + 插入排序的混合算法。
- 平均复杂度：O(n log n)
- 稳定性：稳定
🧠 四、总结对比图（记忆导图）
- Author:🐲🦄😁😄
- URL:https://tengda.us.kg//article/2a90baa9-c0d2-80fe-9a59-c7a191b0c89f
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
