希尔插入排序——过程
设待排序共有10个记录，其关键字分别为47, 33, 61, 82, 71,
11, 25, 47, 57, 02，增量序列取值依次为5, 3, 1。
排 序
希尔插入排序——特点
希尔排序实质上还是一种插入排序，其主要特点是： 每一趟以不同的增量进行排序。在每趟的插入排序中，记录 的关键字是和同一组中的前一个关键字进行比较，所以关键
排 序
3、排序的基本操作
排序的概念：就是要整理文件中的记录，使之按关键字 递增(或递减)次序排列起来。
排序过程的组成步骤：首先比较两个关键字的大小； 然 后将记录从一个位置移动到另一个位置。 对记录的关键字大小进行比较 将记录从一个位置移动到另一个位置 当待排序记录的关键字均不相同时，则排序结果是唯一 的，否则排序的结果不一定唯一。
3．将L.r[i] 插入到L.r[j+1]的位臵上。
具体方法：先将第一个数据看成是一个有序的子序列， 然后从第2个数据起逐个插入到这个有序的子序列中去， 相应的元素要移动。
排 序
例：
待排元素序列：[53] 第一次排序： 第二次排序： 第三次排序： 第四次排序： 第五次排序： [27 [27 [15 [15 [15 27 53] 36 27 27 27 36 36 53] 36 36 36 15 15 15 53] 53 42 69 69 69 69 69] 53 42 42 42 42 42 69] 对于有n个数 据元素的待排 序列，插入操 作要进行n-1 次
有序序列L.r[1..i-1]
L.r[i]
无序序列 L.r[i..n]
有序序列L.r[1..i]
无序序列 L.r[i+1..n]
排 序
方法：
1．在L.r[1..i-1]中查找L.r[i]的插入位臵，
L.r[1..j] L.r[i] < L.r[j+1..i-1]；
2．将L.r[j+1..i-1]中的所有记录均后移 一个位臵；
#include "stdio.h" #define max 10 int data[max+1]; int index[max+1]; int i;
排 序 void shell_sort(a) int a[max+1]; { int i,j,n,m,skip; int alldone; for (i=1;i<=max;i++) index[i]=i; skip=max; while (skip>1) { skip=skip/2; do { alldone=1; for (j=1;j<=max-skip;j++) { i=j+skip; n=index[i]; m=index[j]; if (a[n]<a[m]) { index[i]=m; index[j]=n; alldone=0; } } } while (alldone==0); } }
排 序
1.4 内部排序
一、基本概念
二、插入排序 三、交换排序 四、选择排序 五、归并排序
排 序
一、基本概念
1. 排序的功能：将一个数据元素（或记录） 的任意序列，重新排成一个按关键字有序 的序列。
例如：下列是一组记录对应的关键字序列 (52, 49, 80, 36, 14, 58, 61, 23, 97, 75) 调整为 (14, 23, 36, 49, 52, 58, 61 ,75, 80, 97)
排 序
性能分析
最好情况（原始记录按关键字有序排列）：O（n）
“比较”的次数： n
i 2
“移动”的次数： 0
1 n 1
最坏情况（原始记录按关键字逆序排列）：O（n2） “比较”的次数： “移动”的次数：
n

(n 4)(n 1) (i 1) 2 i2
(n 4)(n 1) (i 1) 2 i 2
排 序
main() { printf("请输入数据: "); for (i=1;i<=max;i++) scanf("%d",&data[i]); printf("\n"); for (i=1;i<=max;i++) printf("%d ",data[i]); printf("\n"); shell_sort(data); for (i=1;i<=max;i++) printf("%d ",data[index[i]]); printf("\n"); }
然后取第二个增量d2<d1，重复上述的分组和排序， 直至所取的增量dt=1 (dt<dt1<…<d2<d1)为止，此时，所 有的记录放在同一组中进行直接插入排序。
排 序
如何选择增量序列才能产生最好的排序效果，这个问
题至今没有得到解决。 希尔本人最初提出取 d1=n/2， di+1=di/2， dt=1，t=log2n。
线性插入排序示例
该算法适合于n 较 小的情况，时间复 杂度为O(n2).
排 序
插入算法
方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的 位置。 void insertSort(RedType L[ ],int n)
{ int i ,j;
for(i=2; i<=n; i++) { L[0]=L[i]; for( j=i-1; L[0].key<L[j].key; j ) L[j+1]=L[j]; L[j+1]=L[0]; }} //记录后移 // 插入 // 作为监视哨
排 序
本节基本内容与要求
基本内容 顺序查找、二分查找、二叉树查找以及散列表上查找 及算法思想 排序的基本概念以及选择、插入、交换和归并四类排 序的基本思想和算法 要求 掌握线性表、树和散列表(或称哈希表)的查找方法及 算法实现以及各种查找方法的应用 熟练掌握选择、插入、交换和归并四类排序的基本思 想和算法
字较小的记录在排序过程中是作跳跃式的移动。
另外，由于开始时增量的取值较大，每组中记录较少， 故排序比较快，随着增量值的逐步变小，每组中的记录逐渐
变多，但由于此时记录已基本有序了，因次在进行最后一趟
增量为1的插入排序时，只需作少量的比较和移动便可完成 排序，从而提高了排序速度。
排 序
希尔插入排序——性能效率
排 序
希尔插入排序——步骤
（1）首先选取一个整数d1<n（n为待排序数据的个数）， 作为两个数据之间的距离，这样把全部数据分成d1个 组，凡是距离为d1的数据放在一个组里，在各组内进 行内部排序，直到各组排好序为止。
（2）从上述的结果序列出发，再选择d2<d1，重复上面的 分组与排序工作。 （3）依次取di+1<di，直到dm=1（设一共需要m次分组）， 即所有数据放在一组中排序为止。此时，全部数据便 按次序排好了。
排 序
5、排序的分类
内部排序：是指在排序的整个过程中，数据全部存放 在计算机的内存储器里，并且在内存储器里调整数据 的位置；
当文件很大以致内存不足以存放全部数据时，在排序 过程中需要对外存进行存取访问，称这种借助于外存 储器进行排序的方法为外部排序。 注意： ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多，不能一次将其 全部记录放入内存的大文件。
直接插入排序的程序： #include "stdio.h" #define n 5 int ar[n]; int c,t; void d_insort(a) int a[n]; { int i,j; for (i=2;i<=n;i++) { t=a[i]; j=i-1; while ((j>0) && (t<a[j])) {a[j+1]=a[j]; j=j-1;} a[j+1]=t; } }
排 序
2. 希尔排序
运行结果：
请输入数据: 19 41 11 17 47 43 13 37 31 23
19 41 11 17 47 43 13 37 31 23 11 13 17 19 23 31 37 41 43 47 希尔排序的分析较为复杂，因为它的时间是所取 “增量”序列的函数，这涉及到一些数学上尚未解决的 难题。增量序列可以有各种取法，但需注意：应使增量 序列中的值没有除 1以外的公因子，并且最后一个增量 值必须等于1。
希尔排序比直接插入排序的平均性能要好： 在最好情况（原始记录按关键字有序排列）下， 移动次数为0，比较次数界于n～ n2 之间。 在最坏情况（原始记录按关键字逆序排列）下， 移动次数和比较次数接近n2。 在平均情况下，移动次数和比较次数在O（n1.3） 左右，好于直接插入排序。
排 序
例1.19 希尔排序的程序
排 序
二、插入排序
每次将一个待排序的记录，按其关键字大小插入到前面 已经排好序的子文件中的适当位置，直到全部记录插入 完成为止。 把新元素（未排序的元素的关键字）逐个插入正在增长 的顺序表中。 寻找插入位置的方法：
线性插入排序
对半插入排序 希尔排序
排 序
1、线性插入排序
基本思想：每步将一个待排序的元素按其大小插入到 前面已排序的数据中的适当位置。重复该工作，直至 有序区包含所有元素。
比较相邻记录，将关 键字最大的记录交换 到 n-i+1 的位臵上
无序序列L.r[1..n-i]
第 i 趟冒泡排序
有序序列 L.r[n-i+1..n]