【排序】各类排序算法的时间性能比较

基于各类排序算法的时间性能比较。

• 用 https://www.luogu.com.cn/paste/nzx555us 中代码
  • 在此题运行
  • 时限 $\tt 1s$，空间限制 $\tt 256MB$。

	插入排序	冒泡排序	选择排序	希尔排序	快速排序	归并排序	堆排序	计数排序	桶排序	基数排序	std::sort
$n=10^3$ 随机数据 $a_i \le 10^5$	$\tt 4ms$	$\tt 7ms$	$\tt 6ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$
$n=10^3$ 完全正序 $a_i \le 10^5$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$
$n=10^3$ 完全倒序 $a_i \le 10^5$	$\tt 4ms$	$\tt 8ms$	$\tt 8ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$	$\tt 4ms$
$n=10^4$ 随机数据 $a_i \le 10^5$	$\tt 80ms$	$\tt 373ms$	$\tt 200ms$	$\tt 7ms$	$\tt 6ms$	$\tt 6ms$	$\tt 7ms$	$\tt 5ms$	$\tt 8ms$	$\tt 5ms$	$\tt 6ms$
$n=10^4$ 随机数据 $a_i \le 10^5$	$\tt 80ms$	$\tt 372ms$	$\tt 198ms$	$\tt 7ms$	$\tt 5ms$	$\tt 6ms$	$\tt 7ms$	$\tt 5ms$	$\tt 7ms$	$\tt 5ms$	$\tt 6ms$
$n=10^4$ 完全正序 $a_i \le 10^5$	$\tt 79ms$	$\tt 5ms$	$\tt 4ms$	$\tt 5ms$	$\tt 5ms$	$\tt 6ms$	$\tt 6ms$	$\tt 5ms$	$\tt 7ms$	$\tt 5ms$	$\tt 5ms$
$n=10^4$ 完全倒序 $a_i \le 10^5$	$\tt 101ms$	$\tt 407ms$	$\tt 394ms$	$\tt 5ms$	$\tt 5ms$	$\tt 5ms$	$\tt 7ms$	$\tt 5ms$	$\tt 7ms$	$\tt 5ms$	$\tt 5ms$
$n=10^5$ 随机数据 $a_i \le 10^6$	TLE	TLE	TLE	$\tt 52ms$	$\tt 28ms$	$\tt 29ms$	$\tt 40ms$	$\tt 19ms$	$\tt 44ms$	$\tt 22ms$	$\tt 30ms$
$n=10^6$ 随机数据 $a_i \le 10^7$	TLE	TLE	TLE	$\tt 683ms$	$\tt 275ms$	$\tt 294ms$	$\tt 438ms$	$\tt 174ms$	$\tt 517ms$	$\tt 216ms$	$\tt 313ms$
$n=10^6$ 随机数据 $a_i \le 10^8$	TLE	TLE	TLE	$\tt 726ms$	$\tt 290ms$	$\tt 311ms$	$\tt 456ms$	MLE	$\tt 610ms$	$\tt 244ms$	$\tt 321ms$
总时间	$\tt \color{red}{352ms}$	$\color{red}{\tt 1176ms}$	$\color{red}{\tt 814ms}$	$\tt 1497ms$	$\tt 626ms$	$\tt 669ms$	$\tt 973ms$	$\color{red}{\tt 225ms}$	$\tt 1212ms$	$\tt 514ms$	$\tt 698ms$

总结：当值域较小时，计数排序无疑是最佳选择，在所有 AC 的算法中时间的比较：

基数排序 $<$ 快速排序 $<$ 归并排序 $<$ std::sort $<$ 堆排序 $<$ 桶排序 $<$ 希尔排序。