选择排序思维脑图思维导图
简单选择排序与堆排序等内容讲解
树图思维导图提供 选择排序思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 选择排序思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：338edc269f45a7a566a1785da1c11a06
思维导图大纲
选择排序思维导图模板大纲
简单选择排序
思想
每一趟在待排序元素中选择关键字最小（大）的元素加入有序子序列
代码
理解过程的关键，背
算法效率
空间复杂度
O(1)
时间复杂度
O(n^2)，比n(n-1)/2次
第i趟（i=1，2……n-1）选出具有最小排序码元素所需比较次数为n-i次
移动次数是O(n)，比较次数O(n^2)
最好不移动，最坏移动RMN =3（n-1）次
不稳定
适用于顺序表、链表
相同情况下，移动次数 < 直接插入排序
堆排序
堆
顺序存储的“完全二叉树”
大根堆：根 ≥ 左、右 ；小根堆：根 ≤ 左、右
思想
建堆
自底向上处理所有非终端节点（从⌊n/2⌋到1），若不满足根≥左、右，将当前节点与更大的孩子交换，若互换后破坏了大根堆（以互换后为结果的下一级堆），即小元素继续“下坠”
举例，如本图53与87互换后，53破坏了堆的结构，让53继续下坠
举例，如本图53与87互换后，53破坏了堆的结构，让53继续下坠
排序
每趟（共n-1趟）将堆顶与待排序中最后一个交换；并再次调整为大根堆；
基于大根堆得到递增序列；基于小根堆得到递减序列；
如果想大根堆降序排列，就每趟输出堆顶元素，再把堆底交换到堆顶，调整大根堆
代码
必须会背，重中之重
分为3部分
建堆：
从len/2到1处理所有非终端结点，注意这里数组是从1开始的
调整以k为根的子树为大根堆
参数中len代表数组长度
循环内，先比较左右孩子，右孩子大则i++
然后比较当前结点和i，若根大，不必处理；否则，A[k] = A[i]
然后k = i，这里k其实是在找根应该插到哪，因为有可能会一直向下调整
所以在循环结束时才给A[k]赋值以前根的位置
堆排序
第一步先建堆！
n-1趟循环中，每趟交换堆顶和堆底，所以i从len到2倒着数
交换后调用调整函数，调整以1为根，大小为i-1的堆
效率分析
空间复杂度
O(1)
时间复杂度
建堆O(n)
建堆的过程，关键字对比次数不超过4n
排序O(nlogn)
总O(nlogn)
不稳定
增删比较
插入
新元素放在堆底
“上升”至无法继续上升
删除
被删元素用堆底元素替代
“下坠”到无法继续下坠
关键字对比次数
“上升”对比1次
“下坠”对比2次（2个孩子） or 1次（1个孩子）
向上调整时，比较次数最多是树高-1，即⌊logn⌋次，即增删操作时间复杂度O(logn)
堆的补充内容
小根堆中关键字最大的记录一定在叶子中，也就是⌊n/2⌋+1 ~ n中
堆新插入的结点如果有兄弟，一定不用比，只需要和父节点比就可以
如果只想要前k小元素：
可以用冒泡、简单选择、堆
k≥5时堆最佳
做法：例如从1亿个数选100个最大值（2023真题）
使用一个大小100的数组，读入前100个数，建立小根堆
依次读入剩余的数，小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆；最后堆中100个数即为所求
相关思维导图模板
树图思维导图提供 发电厂电气部分模块划分思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 发电厂电气部分模块划分思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：d19c03d1be8cb7ef7f63d2705151b362
树图思维导图提供 解决自卑问题思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 解决自卑问题思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f24b9de40cec41d332a3b50565b4f6e4
沪公网安备 31011502019485号
上海工商