各种内部排序方法比较
| 类别 | 排序 | best | normal | worst | 辅助空间 | 稳定性 | 比较次数 | 交换次数 |
|---|---|---|---|---|---|---|---|---|
| 插入 | 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | n-1,n(n-1)/2 | 0,n(n-1)/2 |
| 插入 | 希尔排序 | O(n) | O(n^1.3) | O(n²) | O(1) | 不稳定 | ? | ? |
| 选择 | 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | n(n-1)/2 | 0,n-1 |
| 选择 | 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | nlog2n | ? |
| 交换 | 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | n-1,n(n-1)/2 | 0,n(n-1)/2 |
| 交换 | 快速排序 | O(nlog2n) | O(nlog2n) | O(n²) | O(nlog2n) | 不稳定 | nlog2n,n(n-1)/2 | ? |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | nlog2n/2 | ? | |
| 基数排序 | O(d(n+rd) | O(d(n+rd)) | O(d(n+rd)) | O(rd+n) | 稳定 | ? | ? |
注：基数排序中d代表长度，r代表关键字基数，n代表关键字个数