一句话答案

快排 O(nlogn) 平均最快但不稳定，归并 O(nlogn) 稳定但需额外空间，堆排 O(nlogn) 原地但不稳定。

核心要点

算法	平均	最坏	空间	稳定
快排	O(nlogn)	O(n²)	O(logn)	❌
归并	O(nlogn)	O(nlogn)	O(n)	✅
堆排	O(nlogn)	O(nlogn)	O(1)	❌
冒泡	O(n²)	O(n²)	O(1)	✅
插入	O(n²)	O(n²)	O(1)	✅

快排核心： 选 pivot → partition → 递归 场景选择： 大数据快排，需稳定归并，TopK 用堆

追问与易错

追问方向：

• 快排最坏情况 O(n2) 怎么避免？
• 稳定性为什么重要？
• 面试手写快排关键点？

易错点：

• ❌ 快排在所有场景最快——有序数组退化到 O(n2)
• ❌ 所有 O(nlogn) 排序效果一样——稳定性和空间不同

💡 记忆锚点

排序三巨头都是O(nlogn)但各有脾气：快排像赌徒（平均最快但最坏O(n2)，不稳定，选pivot靠运气），归并像会计（稳定有序不翻车，但要多一份空间O(n)），堆排像苦行僧（原地O(1)空间但不稳定且缓存不友好）。口诀：大数据用快排，要稳定用归并，要原地用堆排。有序数组快排会退化，用随机pivot或三路快排避免。