排序算法的补充思维脑图思维导图
算法比较，排序等相关内容讲解
树图思维导图提供 排序算法的补充思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 排序算法的补充思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：27d73268b338673e4968b95d52c4d1c6
思维导图大纲
排序算法的补充思维导图模板大纲
算法复杂度与初始状态无关
简单选择排序
堆排序
归并排序
基数排序
元素总比较次数与初始状态无关
简单选择排序
基数排序
折半插入排序
元素总移动次数与初始状态无关
归并排序
基数排序
排序趟数与初始状态有关
冒泡排序
快速排序
精检排序
一堆数字不进行两次及以上的比较
直接插入排序
折半插入排序
归并排序
不稳定排序的反例
无论是快排、简单选择、堆、希尔，都可以用
【2，2，1】
各算法比较
希尔排序时间复杂度无视
计数排序
思想
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
计数排序要求输入的数据必须是有确定范围的整数。
用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理
实现逻辑
① 找出待排序的数组中最大和最小的元素 ② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 ③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） ④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
例如
性能
n是0~k的整数
空间复杂度
O(k)
时间复杂度
O(n + k)
稳定
不基于比较的排序
桶排序
思想
将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。
例如
看看得了
性能
空间复杂度
O(n+k)
时间复杂度
最好O(n + k)
最坏O(n ^ 2)
平均O(n + k)
稳定
不基于比较
补充
初态反序，直插、冒泡、简选哪个更好？
简选，rmn最小
n个不同元素集合，同时找最大最小元素至少比较多少次？
第一次先取2个元素，大放max，小放min
第2次及以后，取元素先比max再比min，至少n-1次比较
分配排序
最低位优先更简单
最高位优先每轮额外一个数组或递归，继承高位排序结果
归并排序和快速排序用分治法
相关思维导图模板
树图思维导图提供 1107文家市玉萍思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 1107文家市玉萍思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ed943ef641f6dc874860eb6095857ed6
树图思维导图提供 种子思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 种子思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：86f8307a40ea24607c6c79354e09377f
沪公网安备 31011502019485号
上海工商