| 名称 | 平均时间复杂度 | 额外空间复杂度 | in-place | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(1) | true | 稳定 |
| 选择排序 | O(n2) | O(1) | true | 不稳定 |
| 插入排序 | O(n2) | O(1) | true | 稳定 |
| 归并排序 | O(n * log n) | O(n) | false | 稳定 |
| 快速排序 | O(n * log n) | O(log n) | true | 不稳定 |
| 希尔排序 | O(n1.3) | O(1) | true | 不稳定 |
| 堆排序 | O(n * log n) | O(1) | true | 不稳定 |
| 计数排序 | O(max(n,范围)) | O(范围) | false | 稳定 |
| 基数排序 | O(p(n+b)) | O(n+b) | false | 稳定 |
| 桶排序 | O(n + n(log n - log m)) | O(m+n) | false | 依赖于桶内排序 |
冒泡排序：n比较小时考虑采用、实现简单但速度慢、每次只移动相邻两个元素
选择排序：n比较小时考虑采用、实现简单但速度慢、移动次数较少但不稳定、数据不敏感
插入排序：n比较小时考虑采用、实现简单但速度慢、由于元素移动代价小于元素交换代价所以速度略优于冒泡排序、n越小越有序效率越高
归并排序：n比较大时考虑采用、数据不敏感、需要O(n)额外空间
快速排序：n比较大时考虑采用、速度快元素移动少但不稳定、序列越乱，效率越高
希尔排序：在中小型数组中效率特别快、比较是其中最主要的操作、不稳定
堆排序：适合处理海量数据、不稳定、数据不敏感
计数排序：当数据范围比较小时速度非常快
基数排序：适合多关键字排序
桶排序：当范围已经知道，而且空间不是很重要的情况下考虑采用桶排序