排序算法对比

排序算法对比

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	原址排序	比较排序	稳定
插入排序	$\Theta \left( n^{2} \right)$	$\Theta \left( n \right)$	$\Theta \left( n^{2} \right)$	$\mathbf{O} \left( 1 \right)$	是	是	是
归并排序	$\Theta \left( n \lg n \right)$	$\Theta \left( n \lg n \right)$	$\Theta \left( n \lg n \right)$	$\mathbf{O} \left( n \right)$	否	是	是
堆排序	$\mathbf{O} \left( n \lg n \right)$	$\mathbf{O} \left( n \lg n \right)$	$\mathbf{O} \left( n \lg n \right)$	$\mathbf{O} \left( 1 \right)$	是	是	否
快速排序	$\Theta\left( n \lg n \right)$	$\Theta\left( n \lg n \right)$	$\Theta \left( n^{2} \right)$	$\mathbf{O} \left( \lg n \right)$	是	是	否
计数排序	$\Theta \left( n + k \right)$	$\Theta \left( n + k \right)$	$\Theta \left( n + k \right)$	$\mathbf{O} \left( k \right)$	否	否	是
基数排序	$\Theta \left( d \left( n + k \right) \right)$	$\Theta \left( d \left( n + k \right) \right)$	$\Theta \left( d \left( n + k \right) \right)$	$\mathbf{O} \left( n + k \right)$	否	否	是
桶排序	$\Theta \left( n + k \right)$	$\Theta \left( n + k \right)$	$\Theta\left( n^{2} \right)$	$\mathbf{O} \left( n + k \right)$	否	否	是

稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面；

• 在最坏情况下，任何比较排序算法都需要做 $\Omega \left( n \lg n \right)$ 次比较。

• 比较排序渐进最优：堆排序、归并排序

• 局部或整体有序：插入排序变快、快速排序变慢

• n 较小，不要求稳定性：选择排序

• n 较小，要求稳定性：插入、冒泡排序

• 关键字在有限范围内，空间允许：桶排序

• n 较大，关键字比较随机，不要求稳定性：快速排序

• n 较大，关键字可能出现本身是有序的，要求稳定性，空间允许：归并排序

• n 较大，关键字可能出现本身是有序的，不要求稳定性：堆排序

链表：最坏情况下的仅仅运行时间

unsorted, singly linked	sorted, singly linked	unsorted, doubly linked	sorted, doubly linked
$\text{SEARCH(L, k)}$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$
$\text{INSERT(L, x)}$	$\Theta(1)$	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$
$\text{DELETE(L, x)}$	$\Theta(n)$	$\Theta(n)$	$\Theta(1)$	$\Theta(1)$
$\text{SUCCESSOR(L, x)}$	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$	$\Theta(1)$
$\text{PREDECESSOR(L, x)}$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(1)$
$\text{MINIMUM(L)}$	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$	$\Theta(1)$
$\text{MAXIMUM(L)}$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$