丘卡的秘密小屋

2025-03-29

排序算法经常在笔试和面试中考到，大部分会问平均时间复杂度、空间复杂度、稳定性和是否原地排序的性质，还有少部分会问到最优、最差时间复杂度，神烦无比。而网上的总结又五花八门、莫衷一是，因而自己也收集材料整理一番，虽然无法做到特别全面，但也希望能覆盖大部分的情况。

排序算法	平时时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度¹	原地排序	稳定性
选择排序²	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	不稳定
冒泡排序	$\Omicron(n^2)$	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	稳定
插入排序	$\Omicron(n^2)$	$\Omicron(n)$	$\Omicron(n^2)$	$\Omicron(1)$	原地	稳定
希尔排序³	-	-	-	$\Omicron(1)$	原地	不稳定
快速排序	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n^2)$	$\Omicron(1)$	原地	不稳定
归并排序⁴	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n)$	非原地	稳定
堆排序⁵	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(n\log(n))$	$\Omicron(1)$	原地	不稳定
计数排序⁶	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n+k)$	非原地	稳定
桶排序⁷	$\Omicron(n+k)$	$\Omicron(n+k)$	$\Omicron(n^2)$	$\Omicron(n+k)$	非原地	稳定
基数排序⁸	$\Omicron(mn)$	$\Omicron(mn)$	$\Omicron(mn)$	$\Omicron(n)$	非原地	稳定