当前位置：首页 > article >正文

场景速记排序算法

article 2025/2/13 17:26:39

排序算法	场景描述	时间复杂度	空间复杂度
冒泡排序	煮汤时，气泡不断往上冒，最大的气泡浮到最上面。	最好：O(n)O(n)	O(1)O(1)
		平均：O(n2)O(n2)
		最坏：O(n2)O(n2)
选择排序	整理书架，每次选出最薄的书放到书架上。	最好：O(n2)O(n2)	O(1)O(1)
		平均：O(n2)O(n2)
		最坏：O(n2)O(n2)
插入排序	打扑克牌，每次拿到一张新牌，插入到手中已经排好序的牌中。	最好：O(n)O(n)	O(1)O(1)
		平均：O(n2)O(n2)
		最坏：O(n2)O(n2)
归并排序	整理文件，先把文件分成两半，分别整理好，再合并成一个有序的文件堆。	最好：O(nlog⁡n)O(nlogn)	O(n)O(n)
		平均：O(nlog⁡n)O(nlogn)
		最坏：O(nlog⁡n)O(nlogn)
快速排序	整理书架，选一个基准书，把比它薄的书放左边，比它厚的书放右边，再递归排序。	最好：O(nlog⁡n)O(nlogn)	O(log⁡n)O(logn)
		平均：O(nlog⁡n)O(nlogn)
		最坏：O(n2)O(n2)
堆排序	整理箱子，先把箱子堆成一个“堆”，然后每次从堆顶取出最大的箱子，再调整堆。	最好：O(nlog⁡n)O(nlogn)	O(1)O(1)
		平均：O(nlog⁡n)O(nlogn)
		最坏：O(nlog⁡n)O(nlogn)
计数排序	整理颜色相同的积木，先数一数每种颜色的积木有多少，再按顺序摆放。	最好：O(n+k)O(n+k)	O(k)O(k)
		平均：O(n+k)O(n+k)
		最坏：O(n+k)O(n+k)
基数排序	整理扑克牌，先按花色排序，再按数字排序。	最好：O(n×k)O(n×k)	O(n+k)O(n+k)
		平均：O(n×k)O(n×k)
		最坏：O(n×k)O(n×k)
桶排序	整理大小不一的球，先把球分到不同的桶里，再对每个桶里的球排序。	最好：O(n+k)O(n+k)	O(n+k)O(n+k)
		平均：O(n+k)O(n+k)
		最坏：O(n2)O(n2)

总结记忆技巧：

时间复杂度：				空间复杂度：

冒泡、选择、插入：最坏 O(n2)O(n2)。				冒泡、选择、插入、堆：原地排序 O(1)O(1)。
归并、堆、快速：平均 O(nlog⁡n)O(nlogn)。				归并、计数、基数、桶：需要额外空间 O(n)O(n) 或 O(k)O(k)。
计数、基数、桶：线性或接近线性 O(n+k)O(n+k)。				快速排序：递归栈空间 O(log⁡n)O(logn)。