排序算法整体对比 - 题目详情 - Boyacoding

ID: 387

客观题

难度: 1

上传者:

标签>

教程

排序算法对比

排序算法	均摊复杂度	最好	最坏	空间复杂度 $^{[1]}$	稳定性
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序		$O(n)$			稳定
插入排序		$O(n)$
计数排序	$O(n+k)$			$O(k)$ $^{[2]}$
归并排序	$O(n\log_{2}{n})$		$O(n\log_{2}{n})$	$O(n)$
快速排序			$O(n^2)$	$O(\log_{2}{n})$	不稳定
堆排序			$O(n\log_{2}{n})$	$O(1)$	不稳定

$[1]$ 注：表中空间复杂度指占用数组外部空间。

$[2]$ 注：此处 $k$ 指的是额外数组大小，取决于原数组值域。