8.1排序的基本概念
定义评价指标分类总结 8.2 插入排序
8.2.1插入排序
算法实现算法实现（带哨兵）算法效率分析 8.2.2折半插入排序
对链表进⾏插⼊排序总结 8.2.3希尔排序
算法实现算法性能分析总结 8.3 交换排序
8.3.1冒泡排序
算法实现算法性能分析冒泡排序也适⽤于链表总结 8.3.2快速排序
算法实现算法性能分析总结 8.4选择排序
8.4.1简单选择排序
算法实现算法性能分析总结 8.4.2堆排序
堆的定义建⽴⼤根堆算法实现算法性能分析总结 8.4.3堆的插入删除
插入删除总结 8.5归并排序和基数排序
8.5.1 归并排序
算法实现算法性能分析总结 8.5.2 基数排序
算法性能分析应用总结 8.6
8.6.1外部排序
外存、内存之间的数据交换时间开销分析优化：多路归并多路平衡归并？总结 8.6.2败者树
构造败者树在多路平衡归并中的应⽤（多考察手算，不考察代码） 8.6.3置换-选择排序
总结 8.6.4最佳归并树
构造2路归并的最佳归并树多路归并的最佳归并树添加虚断的数量总结
8.1排序的基本概念 定义 评价指标 分类 总结 8.2 插入排序 8.2.1插入排序算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。
思路：先⽤折半查找找到应该插⼊的位置，再移动元素
⽐起“直接插⼊排序”，⽐较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n²)
移动元素的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
总结 8.2.3希尔排序思想：先追求表中元素部分有序，再逐渐逼近全局有序
思想：从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。
思想：在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上
思想：每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列
基于“⼤根堆”的堆排序得到“递增序列”
建堆的过程，关键字对⽐次数不超过4n，建堆时间复杂度=O(n)
归并：把两个或多个已经有序的序列合并成⼀个
核⼼操作：把数组内的两个有序序列归并为⼀个
两个元素相等时，优先使⽤靠前的那个（稳定性）
k越⼤，r越⼩，归并趟数越少，读写磁盘次数越少
结论：若能增加初始归并段的⻓度，则可减少初始归并段数量 r
败者树——可视为⼀棵完全⼆叉树（多了⼀个头头）。k个叶结点分别是当前参加⽐较的元素，⾮叶⼦结点⽤来记忆左右⼦树中的“失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点。
基于已经构建好的败者树，选出新的胜者只需进⾏ 3场⽐赛
