10大排序算法动态图
- https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg
冒泡排序
插入排序
- 类似于摸牌
- 手上的牌是排好序的（0张和1张天然是排好序的）
- 摸一张，就从左到右找到第一张比他大的，然后插入
- 也可以从大往小比较
- 这样等排摸完，就排好序了
- 如果牌是正好按对的方向排好的，那几乎不用花时间
- 如果是正好按反方向排好的，那每次都要花最多的时间去插入
选择排序
- 老师喜欢矮个的学生
- 你们谁，最矮，过来
- 你们谁，最矮，过来
- 你们谁，最矮，过来
- …..
希尔排序法
- 大家分成左右2队
- 各自从1开始报数
- 号码一样的，按上面从大到小比较的插入法排序下
- 排好了是吧
- 现在分成4队
- 报数，同号的，按上面从大到小比较的插入法排序下
- 现在分8队
- …..
- 每次队伍大概率是快排好了的
- 所以插入效率会越来越高
归并排序
- 假设一个公司：
- 每个分公司有两个大区经理
- 每个大区经理管两个省份
- 每个省份只在两个城市有团队
- 每个团队有两个小组
- 每个小组有两个导购
- 现在想把公司的所有导购的业绩进行排行
- 总共公司告诉分公司，你们先各自排好上报上来，然后他自己每次从两个排行里选绩效最好的就排好了
- 分公司告诉大区经理，你们先各自排好上报上来，然后他自己每次从两个排行里选绩效最好的就排好了
- ……
- 市经理告诉小组长，你们先各自排好上报上来，然后他自己每次从两个排行里选绩效最好的就排好了
- 小组长告诉导购，发现导购天然就是排好序的，每次从两个排行里选绩效最好的就排好了
- 接着就是一路上报
快速排序
- 老师随便选了个同学，来比张XX高的去右边，比他矮的去左边
- 然后两边的也随便选个同学，按一样的方式分下
- 分到最后剩一个，自然是排好序的
计数排序
- 一个个看下价格
- 好，最少21愿，最多29
- 划分9个堆
- 一个个往9个堆里丢
- 从9个堆里，一个个拿出来，就排好多了
桶排序
- 预估下数据分布
- 按数据访问划分多个桶
- 将数据都丢到对应的同中
- 每个桶单独进行插入排序
- 按顺序把一个个桶里的数据取出来
- 如果只有一个桶的话，退化为插入排序
- 如果是N个桶的话，退化为计数排序
基数排序
- 补位到相同长度
- 依次按最后一位把数据丢0-9这些桶里
- 按顺序拿出来，再按倒数第二位把数据丢0-9这些桶里
- 按顺序拿出来，再按倒数第三位把数据丢0-9这些桶里
- …..
- 知道最高位，再按倒数第三位把数据丢0-9这些桶里
- 只有一位的话，退化为计数排序