排序算法概述

1. 概念

1.1 原址

如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外,则成排序算法是原址的。

1.2 稳定

在输入数组中,存在多个具有相同的关键字的元素,若经过排序,这些元素的相对次序保持不变,则称这种排序算法是稳定的,否则称为不稳定的。

2. 算法

2.1 比较排序

排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
插入排序 O(n2)O(n^2) O(n2)O(n^2) O(n)O(n) O(1)O(1) 稳定
选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) 不稳定
冒泡排序 O(n2)O(n^2) O(n2)O(n^2) O(n)O(n) O(1)O(1) 稳定
希尔排序 O(n1.3)O(n^{1.3}) O(n2)O(n^2) O(n)O(n) O(1)O(1) 不稳定
快速排序 O(nlog2n)O(n\log_2 n) O(n2)O(n^2) O(nlog2n)O(n\log_2 n) O(log2n)O(\log_2 n)
(平均递归栈层次大小)
不稳定
堆排序 O(nlog2n)O(n\log_2 n) O(nlog2n)O(n\log_2 n) O(nlog2n)O(n\log_2 n) O(1)O(1) 不稳定
归并排序 O(nlog2n)O(n\log_2 n) O(nlog2n)O(n\log_2 n) O(nlog2n)O(n\log_2 n) O(n)O(n) 稳定

2.2 非比较排序

排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
计数排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n+k)O(n+k) O(n+k)O(n+k) 稳定
桶排序 O(n+k)O(n+k) O(n2)O(n^2) O(n)O(n) O(n+k)O(n+k) 稳定
基数排序 O(kn)O(kn) O(kn)O(kn) O(kn)O(kn) O(n+k)O(n+k) 稳定