选择排序思维脑图思维导图

O(1)

O(n^2)，比n(n-1)/2次

移动次数是O(n)，比较次数O(n^2)

最好不移动，最坏移动RMN =3（n-1）次

自底向上处理所有非终端节点（从⌊n/2⌋到1），若不满足根≥左、右，将当前节点与更大的孩子交换，若互换后破坏了大根堆（以互换后为结果的下一级堆），即小元素继续“下坠”

举例，如本图53与87互换后，53破坏了堆的结构，让53继续下坠

每趟（共n-1趟）将堆顶与待排序中最后一个交换；并再次调整为大根堆；

基于大根堆得到递增序列；基于小根堆得到递减序列；

如果想大根堆降序排列，就每趟输出堆顶元素，再把堆底交换到堆顶，调整大根堆

建堆：

调整以k为根的子树为大根堆

堆排序

O(1)

建堆O(n)

排序O(nlogn)

总O(nlogn)

新元素放在堆底

“上升”至无法继续上升

被删元素用堆底元素替代

“下坠”到无法继续下坠

“上升”对比1次

“下坠”对比2次（2个孩子） or 1次（1个孩子）

向上调整时，比较次数最多是树高-1，即⌊logn⌋次，即增删操作时间复杂度O(logn)

可以用冒泡、简单选择、堆

k≥5时堆最佳

做法：例如从1亿个数选100个最大值（2023真题）