序序列
1)将r[i]暂存在r[0] 2) j=i-1；//从第i-1记录开始查找 3)当r[j]>r[0]时，循环做{ r[j]后移一个位置,j--} 4)r[j+1]=r[0] //将r[0]插入到位置j+1
r[0]的作用? 暂存单元 , 监视哨
8.2插入排序
直接插入排序算法
void insertSort (int r[ ], int n)
{
for (i=2; i<=n; i++)
{
r[0]=r[i];
for(j=i-1; r[0]<r[j];j--)
r[j+1]=r[j];
r[j+1]=r[0]; } }
1.i从第2个到第n个记录,做以下循环： 1.1将r[i]暂存在r[0] 1.2 j=i-1； 1.3当r[j]>r[0]时，循环做：
10 21 22 25{ 25* 18 将第i个数插入到有序序列中的
10 18 21 22合理2位5 置25*
}
8.2插入排序
直接插入排序
需解决的关键问题? 对于r[i]，如何查找它的插入位置?如何实现插入？
01 2 345
21 20 212 225 251 26 …… 18
j
j
j
i
1)将r[i]暂存在r[0]
1）直接插入排序 2）希尔排序
举例: 有序序列 2 , 待排序记录 3,6,1
8.2插入排序
8.2.1直接插入排序
基本思想：在插入第 i（i＞1）个记录时，前面的 i-1 个记录已经排好序。
r1 r2
……
ri-1 ri ri+1
……
rn
有序序列 r'1 r'2 ……
有序序列
无序序列
r'i-1 r'i ri+1 ……
学号 0001 0002 0003 …
姓名 王军 李明 汤晓影
…
高数 85 64 85 …
英语 68 72 78 …
思想品德 88 92 86 …
8.1概 述
1.排序的基本概念
正序：待排序序列中的记录已按关键码排好序。 逆序（反序）：待排序序列中记录的排列顺序与排好 序的顺序正好相反。
学号 0001 0002 0003
思想品德 88 92 86 …
8.1概 述
1.排序的基本概念
排序：给定一组记录的集合{r1, r2, ……, rn}，其相应的关 键码分别为{k1, k2, ……, kn}，排序是将这些记录排列成顺 序为{rs1, rs2, ……, rsn}的一个序列，使得相应的关键码满 足非递减关系ks1≤ks2≤……≤ksn（称为升序）或非递增关系 ks1≥ks2≥……≥ksn（称为降序）。
学号 姓名 0002 李 明 0001 王 军 0003 汤晓影 ……
高数 64 85 85 …
英语 72 68 78 …
学号 姓名 0001 王 军 0002 李 明 0003 汤晓影 ……
高数 85 64 85 …
英语 68 72 78 …
8.1概 述
1.排序的基本概念
排序算法的稳定性：假定在待排序的记录集中，存在多 个具有相同键值的记录，若经过排序，这些记录的相 对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之 前，而在排序后的序列中，ri一定在rj之前，则称这种 排序算法是稳定的；否则称为不稳定的。
8.1概 述
2.内排序算法
1. 插入排序 2. 交换排序
3. 选择排序
直接插入排序 希尔排序
冒泡排序 快速排序 简单选择排序 堆排序
4. 归并排序
8.1概 述
3.排序的基本过程
排序基本过程:是一个逐步扩大记录的有序序列长度 的过程
有序序列区 有序序列区
无序序列区
一趟排序
无序序列区
一趟排序:将无序序列区里一个或几个记录合并到有序序列的 过程为一趟排序，有序序列长度增加1个或几个
10 15 24 6 12 35 40 98
假定2：将待排序的记录序列排序为升序序列。
内排序算法
1. 插入排序 2. 交换排序 3. 选择排序 4. 归并排序
8.1概 述
直接插入排序 希尔排序 冒泡排序 快速排序 简单选择排序 堆排序
8.2插入排序
插入排序的主要操作是插入，其基本思想是： 每次将一个待排序的记录按其关键码的大小插 入到一个已经排好序的有序序列中，直到全部 记录排好序为止。
无序序列
2) j=i-1；//从第i-1记录开始查找
3)当r[j]>r[0]时，循环做{ r[j]后移一个位置,j--}
4)r[j+1]=r[0] //将r[0]插入到位置j+1
8.2插入排序
直接插入排序
需解决的关键问题? 对于r[i]，如何查找它的插入位置?如何实现插入？
01 2 345
10 120 202 225 2150 25 …… 18
rn
无序序列
8.2插入排序
直接插入排序过程示例
r0 1 2 3 4 5 6
第一趟 第二趟 第三趟 第四趟 第五趟
21 25 22 10 25* 18 算法稳定吗？
21 25 22 10 25* 18
共多少趟？
21 22 25 10 25* 18
算法思想？
10 21 22 25 25* 18 i从第2个数到第n个数
第八章 排序技术
本章的基本内容是：
➢排序的基本概念 ➢插入排序 ➢交换排序 ➢选择排序
8.1概 述
1.排序的基本概念
排序：将一组“无序”的记录序列,调整为按关键字“有 序”的记录序列.
学号 0002 0001 0003 …
姓名 王军 李明 汤晓影
…
高数 85 64 85 …
英语 68 72 78 …
大家有疑问的，可以询问和交流
可以互相讨论下，但要小声点
8.1概 述
4.排序算法的存储结构
从操作角度看，排序是线性结构的一种操作，待排序 记录可以用顺序存储结构或链接存储结构存储。
假定1：待排序记录采用顺序存储结构，关键码为整 型，且记录只有关键码一个数据项。
01 2 3 4 5 6 7 8
r[n+1]
{ r[j]后移一个位置,j--}
…
姓名 王军 李明 汤晓影
…
高数 85 64 85 …
英语 68 72 78 …
思想品德 88 92 86 …
8.1概 述
1.排序的基本概念
排序的分类
1.内排序：在排序的整个过程中，待排序的所有记录 全部被放置在内存中,不需要访问外存
2.外排序：由于待排序的记录个数太多，不能同时放 置在内存，而需要将一部分记录放置在内存，另一部 分记录放置在外存上，整个排序过程需要在内外存之 间多次交换数据才能得到排序的结果。