排序算法简介及分类
一、排序算法分类
资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
按核心思路可分为几大类，以下是主流算法的简介：
1. 比较类排序（基于元素间比较）
（1）简单排序（入门级，时间复杂度 O(n²)）
冒泡排序
- 思路：重复遍历数组，每次比较相邻元素，若顺序错误则交换，直到没有交换发生（像气泡上浮）。
- 特点：稳定，空间复杂度 O(1)（原地排序），适合小规模数据或近乎有序的数据，最坏情况效率低。
选择排序
- 思路：每次从未排序部分找到最小/最大值，放到已排序部分的末尾。
- 特点：不稳定（交换会打乱相等元素位置），空间复杂度 O(1)，数据移动次数少，但无论数据是否有序，时间复杂度都是 O(n²)。
插入排序
- 思路：将数组分为已排序和未排序部分，逐个将未排序元素插入到已排序部分的正确位置。
- 特点：稳定，空间复杂度 O(1)，对近乎有序的小数据量（如 n<1000）效率极高，实际表现优于冒泡/选择排序。
（2）高级排序（时间复杂度 O(n log n)）
快速排序
- 思路：分治思想，选一个“基准值”，将数组分为“小于基准”和“大于基准”两部分，递归排序子数组。
- 特点：不稳定，空间复杂度 O(log n)（递归栈），实际应用中最快的排序算法（缓存友好），最坏情况（如已排序数据）退化为 O(n²)（可通过随机选基准优化），适合大规模无序数据。
归并排序
- 思路：分治思想，将数组拆分为子数组直到长度为1，再合并两个有序子数组为一个有序数组。
- 特点：稳定，空间复杂度 O(n)（非原地），时间复杂度稳定 O(n log n)，适合需要稳定性、数据量大且对内存要求不苛刻的场景（如外部排序）。
堆排序
- 思路：利用堆（完全二叉树）的特性，构建大顶堆/小顶堆，反复提取堆顶元素放到有序区。
- 特点：不稳定，空间复杂度 O(1)，时间复杂度稳定 O(n log n)，但缓存不友好，实际效率略低于快速排序，适合内存受限的场景。
2. 非比较类排序（不依赖元素比较，时间复杂度 O(n)）
这类算法利用数据的数值特征（如范围、位数），仅适用于特定场景：
计数排序
- 思路：统计每个数值出现的次数，再按数值顺序重构数组。
- 特点：稳定，空间复杂度 O(n+k)（k 为数值范围），仅适用于数值范围较小的整数排序（如 0~100 的分数）。
基数排序
- 思路：按数字的每一位（个位、十位、百位）依次排序（借助计数/桶排序），从低位到高位完成整体有序。
- 特点：稳定，空间复杂度 O(n+k)（k 为基数，如十进制 k=10），适合整数、字符串等按位排序的场景（如手机号、身份证号）。
桶排序
- 思路：将数据分配到多个“桶”中，对每个桶内数据单独排序，最后合并桶。
- 特点：稳定（取决于桶内排序算法），空间复杂度 O(n+k)（k 为桶数），适合数据均匀分布的场景（如 0~1 之间的浮点数）。
二、核心特性对比（简版）
| 算法 | 时间复杂度（平均） | 稳定性 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | 稳定 | O(1) | 小数据、近乎有序 |
| 插入排序 | O(n²) | 稳定 | O(1) | 小数据、近乎有序 |
| 快速排序 | O(n log n) | 不稳定 | O(log n) | 大规模无序数据（主流） |
| 归并排序 | O(n log n) | 稳定 | O(n) | 需稳定、大规模数据 |
| 计数排序 | O(n+k) | 稳定 | O(n+k) | 数值范围小的整数 |
| 基数排序 | O(d(n+k)) | 稳定 | O(n+k) | 多位数、字符串排序 |
三、总结
- 小规模数据：优先选插入排序（实际效率最优）；
- 大规模无序数据：优先选快速排序（综合性能最好）；
- 需稳定性+大规模数据：选归并排序；
- 数值特征明确（如范围小、位数固定）：选非比较类排序（计数/基数/桶排序）。
排序算法是算法入门的核心，理解其思路、复杂度和适用场景，是解决实际开发中数据排序问题的基础。