8.1排序的基本概念

定义

评价指标

分类

总结

8.2 插入排序

8.2.1插入排序

算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。

算法实现

算法实现（带哨兵）

算法效率分析

8.2.2折半插入排序

思路：先⽤折半查找找到应该插⼊的位置，再移动元素


⽐起“直接插⼊排序”，⽐较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n²)

对链表进⾏插⼊排序

移动元素的次数变少了，但是关键字对⽐的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)

总结

8.2.3希尔排序

思想：先追求表中元素部分有序，再逐渐逼近全局有序

算法实现

算法性能分析

总结

8.3 交换排序

8.3.1冒泡排序

思想：从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列⽐较完。称这样过程为“⼀趟”冒泡排序。

算法实现

算法性能分析

冒泡排序也适⽤于链表

总结

8.3.2快速排序

思想：在待排序表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)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上

算法实现

算法性能分析

总结

8.4选择排序

8.4.1简单选择排序

思想：每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列

算法实现

算法性能分析

总结

8.4.2堆排序

堆的定义

建⽴⼤根堆

算法实现

基于“⼤根堆”的堆排序得到“递增序列”

算法性能分析

建堆的过程，关键字对⽐次数不超过4n，建堆时间复杂度=O(n)

总结

8.4.3堆的插入删除

插入

删除

总结

8.5归并排序和基数排序

8.5.1 归并排序

归并：把两个或多个已经有序的序列合并成⼀个


核⼼操作：把数组内的两个有序序列归并为⼀个

算法实现

两个元素相等时，优先使⽤靠前的那个（稳定性）

算法性能分析

总结

8.5.2 基数排序

算法性能分析

应用

总结

8.6

8.6.1外部排序

外存、内存之间的数据交换

时间开销分析

优化：多路归并

k越⼤，r越⼩，归并趟数越少，读写磁盘次数越少

结论：若能增加初始归并段的⻓度，则可减少初始归并段数量 r

多路平衡归并？

总结

8.6.2败者树

构造

败者树——可视为⼀棵完全⼆叉树（多了⼀个头头）。k个叶结点分别是当前参加⽐较的元素，⾮叶⼦结点⽤来记忆左右⼦树中的“失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点。

基于已经构建好的败者树，选出新的胜者只需进⾏ 3场⽐赛

败者树在多路平衡归并中的应⽤（多考察手算，不考察代码）

8.6.3置换-选择排序

总结

8.6.4最佳归并树

构造2路归并的最佳归并树

多路归并的最佳归并树

添加虚断的数量

总结