本章的基本内容是：\r\n\r\n排序的基本概念\r\n插入排序\r\n交换排序\r\n选择排序\r\n归并排序
概 述
排序：给定一组记录的集合{r1, r2, ……, rn}，其相应的关键码分别为{k1, k2, ……, kn}，排序是将这些记录排列成顺序为{rs1, rs2, ……, rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。\r\n正序：待排序序列中的记录已按关键码排好序。\r\n逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。
排序的基本概念
排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
概 述
排序的基本概念
概 述
排序的基本概念
单键排序：根据一个关键码进行的排序；\r\n多键排序：根据多个关键码进行的排序。
按学号排序——单键排序\r\n按成绩（高数＋英语＋思想品德）排序——多键排序
概 述
排序的基本概念
设关键码分别为k1, k2, …, km，多键排序有两种方法：\r\n⑴ 依次对记录进行m次排序，第一次按k1排序，第二次按k2排序，依此类推。这种方法要求各趟排序所用的算法是稳定的；\r\n⑵ 将关键码k1, k2, …, km分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。
排序的分类\r\n1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中\r\n2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。
概 述
排序的基本概念
排序的分类\r\n1. 基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。 \r\n2. 不基于比较：根据关键码的分布特征。
概 述
排序的基本概念
基于比较的内排序\r\n1. 插入排序\r\n2. 交换排序\r\n3. 选择排序\r\n4. 归并排序
1. 基本操作。内排序在排序过程中的基本操作：\r\n⑴比较：关键码之间的比较；\r\n⑵移动：记录从一个位置移动到另一个位置。 \r\n2. 辅助存储空间。\r\n辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。\r\n3.算法本身的复杂程度。
排序算法的性能
概 述
排序算法的存储结构
概 述
从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。
假定2：将待排序的记录序列排序为升序序列。
int r[n 1]; \r\n//待排序记录存储在r[1]~r[n]，r[0]留做他用
假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。
插入排序
插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。
基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。
直接插入排序
插入排序
基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。
（1）如何构造初始的有序序列？\r\n（2）如何查找待插入记录的插入位置?
直接插入排序
插入排序
需解决的关键问题?
直接插入排序过程示例
r 0 1 2 3 4 5 6
21
18
25
22
10
25*
21
插入排序
22
10
25
18
18
r[0]的作用?
暂存单元
监视哨
解决方法：\r\n将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。
插入排序
关键问题(1)如何构造初始的有序序列？
算法描述：\r\nfor (i=2; i<=n; i ) \r\n{ \r\n 插入第i个记录，即第i趟直接插入排序；\r\n}
关键问题(2)如何查找待插入记录的插入位置?
解决方法：\r\n在i-1个记录的有序区r[1] ~ r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。
r[0]有两个作用：\r\n1. 进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容；\r\n2. 在查找插入位置的循环中充当哨兵。
插入排序
算法描述：\r\nr[0]=r[i]; j=i-1; \r\nwhile (r[0]<r[j]) \r\n{\r\n r[j 1]=r[j]; \r\n j--;\r\n}
void insertSort (int r[ ], int n)\r\n{ \r\n for (i=2; i<=n; i )\r\n { \r\n r[0]=r[i]; j=i-1;\r\n while (r[0]<r[j])\r\n { \r\n r[j 1]=r[j]; \r\n j=j-1; \r\n }\r\n r[j 1]=r[0]; \r\n }\r\n}
直接插入排序算法
插入排序
直接插入排序算法性能分析
最好情况下（正序）：
插入排序
时间复杂度为O(n)。
直接插入排序算法性能分析
插入排序
最好情况下（正序）：
最坏情况下（逆序或反序）：
时间复杂度为O(n2)。
时间复杂度为O(n)。
平均情况下（随机排列）：
直接插入排序算法性能分析
插入排序
时间复杂度为O(n2)。
空间性能：需要一个记录的辅助空间。\r\n\r\n直接插入排序算法是一种稳定的排序算法。
直接插入排序算法性能分析
插入排序
直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。\r\n当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。
插入排序
如何改进直接插入排序?
注意到，在插入第 i（i＞1）个记录时，前面的 i-1 个记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而较少比较次数。
请同学们写出这个改进的直接插入排序算法，并分析时间性能。
希尔排序
改进的着眼点：\r\n（1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；\r\n（2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。
插入排序
（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？\r\n（2）子序列内如何进行直接插入排序？
插入排序
需解决的关键问题?
基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。
希尔排序
基本有序：接近正序，例如{1, 2, 8, 4, 5, 6, 7, 3, 9}；\r\n局部有序：部分有序，例如{6, 7, 8, 9, 1, 2, 3, 4, 5}。\r\n局部有序不能提高直接插入排序算法的时间性能。
插入排序
希尔排序
分割待排序记录的目的?
1. 减少待排序记录个数；\r\n2. 使整个序列向基本有序发展。
子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。
启示?
希尔插入排序过程示例
1 2 3 4 5 6 7 8 9
40
21
25
49
25*
16
初始序列
插入排序
30
08
13
解决方法：\r\n将相隔某个“增量”的记录组成一个子序列。\r\n增量应如何取？\r\n希尔最早提出的方法是d1=n/2，di 1=di/2。
关键问题(1)应如何分割待排序记录？
插入排序
算法描述：\r\nfor (d=n/2; d>=1; d=d/2) \r\n{\r\n 以d为增量，进行组内直接插入排序；\r\n}
解决方法：\r\n在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。当搜索位置＜0，表示插入位置已找到。\r\n在搜索过程中，记录后移也是跳跃d个位置。\r\n在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d 1个记录开始进行插入。
插入排序