各排序算法性能比较

2018-07-17 本文已影响0人善法

排序算法	时间复杂度	辅助空间	稳定性	链式结构
直接插入	平均 $O(n^2)$	$O(1)$	稳定	可以
折半插入	平均 $O(n^2)$	$O(1)$	稳定	不可以
希尔排序	平均 $O(n^{1.3})$	$O(1)$	不稳定	不可以
冒泡排序	平均 $O(n^2)$	$O(1)$	稳定	可以
选择排序	$O(n^2)$	$O(1)$	不稳定	可以
快速排序	平均 $O(n\log_2n)$	$O(\log_2n)$	不稳定	不可以
堆排序	$O(n\log_2n)$	$O(1)$	不稳定	不可以
归并排序	$O(n\log_2n)$	$O(n)$	稳定	可以
基数排序	$O(d(n+rd))$	$O(n+rd)$	稳定	可以