6．内排序 整个排序过程都在内存进行的排序称为内排序。
7．外排序 待排序的数据元素量大，以致内存一次不能容纳全部记录，
在排序过程中需要对外存进行访问的排序称为外排序。
本章只讨论内排序。
10.2 插入排序
1.直接插入排序
基本思想： 直接插入排序是一种最简单的排序方法，它的基本操
作是将一个记录插到已排序好的有序表中，从而得到一个 新的，记录数增 1 的有序表。
01 23 4 5 36 24 10 6 12 i
24 24 36
பைடு நூலகம்
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5 36 24 10 6 12 i
10 24 36 10
第10章 排序
10.1 概述
1.排序（Sorting） 将数据元素（或记录）的任意序列，重新排列成一个按关
键 字有序（递增或递减）的序列的过程称为排序。 2. 排序过程中的两种基本操作 （1）比较两个关键字值的大小。 （2）根据比较结果，移动记录的位置。
3.对关键字排序的三个原则 （1）关键字值为数值型的，则按键值大小为依据。 （2）关键字值为ASCII码，则按键值的内码编排顺序为依据。 （3）关键字值为汉字字符串类型，则大多以汉字拼音的字典
01 23 4 5
36 24 10 6 12 i
10
24 36
1、直接插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5 36 24 10 6 12 i
10 10 24 36
与排序前保持一致，则这种排序法是稳定的。 若排序后的序列为：3，3，5，6，6，8
则这种排序法是不稳定的。
5．待排序记录的三种存储方式 （1）待排序记录存放在地址连续的一组存储单元上。 （2）待排序记录存放在静态链表中。 （3）待排序记录存放在一组地址连续的存储单元，同时另
设一个指示各个记录存储位置的地址向量，在排序过程中不移 动记录本身，而移动地址向量中这些记录的“地址”，在排序 结束后，再按照地址向量中的值调整记录的存储位置。
01 23 4 5
36 24 10 6 12 i
6 10 24
36
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5
36 24 10 6 12 i
6 10
24 36
如果所取元素大于等于有序序列的序尾，则保持原存储位置不变。
1、直接插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5 36 24 10 6 12 i
24 36 24
1、直接插入排序
循环： 从未排序序列中依次取一个元素；（循环从i=2,3,4,5...） 取一个元素后进行判断：
如果所取元素小于当前有序序列的序尾，则： （1）将所取元素赋值给r[0]， r[0] 当作哨兵。 （2）循环：
在当前有序序列中寻找自己的位置，进行插入： 从当前有序序列的序尾开始，倒着往前，将哨兵与相应元素逐个比较： 哨兵比当前元素小，当前元素就往后移一个位置；再往前比，若哨 兵比当前元素还小，当前元素再往后移一个位置 ...直到哨兵大于 等于当前元素，循环结束，将哨兵插入到当前元素的后面。
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5 36 24 10 6 12 i
6 10 24 36 6
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5
36 24 10 6 12 i
24
36
1、直接插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
次序为依据。
4.排序方法的稳定和不稳定 若对任意的数据元素序列，使用某个排序方法按关键字进
行排序，对原先具有相同键值元素间的位置关系，若排序前与 排序后保持一致，称此排序方法是稳定的；反之，则称为不稳 定的。
例：对数据键值为：5，3，8，3，6，6，排序。 若排序后的序列为：3，3，5，6，6，8 其相同键值的元素位置依旧是 3 在 3 前，6 在 6 前，
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
整个排序过程为 n-1 趟插入，即先将序列中第 1 个记 录看成是一个有序子序列，然后从第 2 个记录开始，逐个 进行插入，直至整个序列有序。
取要插入的元素，直接插在一个有序序列的合适位置。
01 23 4 5 36 24 10 6 12
排序过程：
将第一个元素 r[1] 作为已排序有序序列； 其他元素r[2],r[3],r[4],r[5],...r[n]作为未排序序列；
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。
01 23 4 5
36 24 10 6 12 i
10 24
36
1、直接插入排序
e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。