主要参考 十大经典排序算法总结（JavaScript描述） 原文更详细
| 名称 | 平均复杂度 | 最差复杂度 | 最优复杂度 | 空间开销 | 是否稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | $O( n^2 )$ | $O( n^2 )$ | $O( n^2 )$ | $O(1) | 是 |
| 选择排序 | $O( n^2 )$ | $O( n^2 )$ | $O( n^2 )$ | $O(1) | 否 |
| 插入排序 | $O( n^2 )$ | $O( n^2 )$ | $O( n^2 )$ | $O(1) | 是 |
| 希尔排序 | $O( n\log(n) )$ | $O( n^2 )$ | $O( n\log_2n )$ | $O(1) | 否 |
| 快速排序 | $O( n\log(n) )$ | $O( n^2 )$ | $O( n\log(n) )$ | $O(1) | 否 |
| 归并排序 | $O( n\log(n) )$ | $O( n\log(n) )$ | $O( n\log(n) )$ | $O(1) | 是 |
| 堆排序 | $O( n\log(n) )$ | $O( n\log(n) )$ | $O( n\log(n) )$ | $O(1) | 否 |
| 计数排序 | $O( n + k )$ | $O( n + k )$ | $O( n + k )$ | $O(1) | 是 |
| 基数排序 | $O( n * k )$ | $O( n * k )$ | $O( n * k )$ | $O(1) | 是 |
| 桶排序 | $O( n + K )$ | $O( n + K )$ | $O( n^2 )$ | $O(1) | 是 |
堆排序中建堆过程的时间复杂度是 $O(n)$
桶排序和基数排序均属于分配排序。分配排序的基本思想：排序过程无须比较关键字，而是通过用额外的空间来”分配”和”收集”来实现排序，它们的时间复杂度可达到线性阶：O(n)。简言之就是：用空间换时间，所以性能与基于比较的排序才有数量级的提高！