一、内部排序的一般分类
1、插入排序
- 直接插入
- ?希尔排序
- ? 折半插入
- ?2-路插入
- ?表插入
2、交换排序
- 冒泡排序
- 快速排序
3、选择排序
- 简单选择
- 树形选择
- ?堆排序
4、归并排序
5、基数排序
二、八大内部排序
1、直接插入排序【稳定】（O（n^2））
?（1）核心思想
? ? ? ? 将数组中的所有元素依次跟前面已经排好的元素相比较，
? ? ? ? 如果选择的元素比已排序的元素小，则交换，再和前一个比较，直到全部元素都比较过。? ??
（2）关键：找到待排序元素要插入到已排序序列的位置【查找】
? ?直接插入：一个个往前比和交换
? ?二分插入：将有序列表进行二分查找，待排的为key，目标序列是已排好的序列
? ? ? ? ? ? ??https://www.bilibili.com/video/BV1Zv411n72E?spm_id_from=333.999.0.0
? ?
2、希尔排序（缩小增量排序）【不稳定】(O(n^1.3))
? ? 找每条线段首尾两个元素中最小的，然后次小的，依次排序
? ? ?
[注]希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多
3、冒泡排序【稳定】(O(n^2))
? ?相邻两个比较，大的往后移，每次循环冒出一个大的，直至最后全部冒出
4、快速排序【不稳定】
? ? ?每次第一个元素为参照物，大的放其后面，小的放其前面
? ?
5、简单选择排序【不稳定】(O(n^2))
? ?每次选择最小的关键字和第一个位置交换
? ?在剩下的元素中再找最小的，再和第二个位置交换
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ....
6、堆排序【不稳定】(O(n*log(2,n)))
?(1)一般步骤：?
? ? ? ?数组--->完全二叉树（根左右顺序）---->从最后一个父节点调整成最大堆
（2）完全二叉树特点：
? ? ? ? ? 左=根*2+1
? ? ? ? ? 右=根2+2
（3）堆的分类：
? ? ??大顶堆：父节点大于所有孩子及其子树上元素
? ? ??小顶堆：父节点小于所有孩子及其子树上元素
??
7、归并排序【稳定】(O(n*log(2,n)))
? 一个序列，两两归并+排序
? ? ?第一趟：两个元素比较
? ? 第二趟：四个元素比较
8、基数排序【稳定】(O(d(n+r)))??d-位数? n-元素个数 r-基数
? （1）特点： 分配+收集
? ? ? 分别按照个位、十位、百位、分配? ? （num/exp）%10? ?exp=10^0? 10^1? ?10^2
? ? ? 每次分配之后收集，得到一个序列，再接着分配?
?
【总结】
?
三、外部排序（了解）
1、多路平衡归并排序（胜者树、败者树）
2、置换选择排序
3、最佳归并树
参考总结：
数据结构常见的八大排序算法（详细整理） - 竹雨听闲 - 博客园
Java零基础自学教程之归并排序_哔哩哔哩_bilibili
《漫画算法 小灰的算法之旅》