Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
【程序员面试必备】动画详解十大经典排序算法
由于待排序的元素数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两类：一类是内部排序，指的是待排序列存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序的元素的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
我们可以将常见的内部排序算法可以分成两类：
比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。属于比较类的有：
| 排序算法 | 时间复杂度 | 最差情况 | 最好情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | In-place | |
| 快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(logn) | In-place | ✘ |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | In-place | |
| 希尔排序 | O(nlog²n) | O(n²) | O(n) | O(1) | In-place | ✘ |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | In-place | ✘ |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | In-place | ✘ |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Out-place |
非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。属于非比较类的有：
| 排序算法 | 时间复杂度 | 最差情况 | 最好情况 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 桶排序 | O(n+nlog(n/r)) | O(n²) | O(n) | O(n+r) | Out-place | |
| 计数排序 | O(n+r) | O(n+r) | O(n+r) | O(n+r) | Out-place | |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | Out-place |
名词解释：
时间复杂度：描述一个算法执行时间与数据规模的增长关系
空间复杂度：描述一个算法占用空间与数据规模的增长关系
n：待排序列的个数
r：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）
d：待排序列的最高位数
In-place：原地算法，指的是占用常用内存，不占用额外内存。空间复杂度为 O(1) 的都可以认为是原地算法
Out-place：非原地算法，占用额外内存
稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。
看完整文章可以直接戳这里