线性插入排序示例
排序
对于有n个数 据元素的待排 序列，插入操 作要进行n-1
次
该算法适合于n 较 小的情况，时间复 杂度为O(n2).
排序
插入算法
方法:Ki与Ki-1,K i-2,…K1依次比较,直到找到应插入的 位置。
void insertSort(RedType L[ ],int n)
{ int i ,j;
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; } }
main() { int i;
printf("请输入数据: "); for (i=1;i<=n;i++)
scanf("%d",&ar[i]); d_insort(ar); printf("排序后的序列: "); for (i=1;i<=n;i++)
{ printf("%d |",ar[i]);
} printf("\n"); }
运行结果： 请输入数据: 50 60 20 40 80 排序后的序列: 20 |40 |50 |60 |80 |
当文件很大以致内存不足以存放全部数据时，在排序 过程中需要对外存进行存取访问，称这种借助于外存 储器进行排序的方法为外部排序。
注意： ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多，不能一次将其 全部记录放入内存的大文件。
排序
二、插入排序
每次将一个待排序的记录，按其关键字大小插入到前面 已经排好序的子文件中的适当位置，直到全部记录插入 完成为止。
L.r[i]
有序序列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]中的所有记录均后移 一个位置； 3．将L.r[i] 插入到L.r[j+1]的位置上。
具体方法：先将第一个数据看成是一个有序的子序列， 然后从第2个数据起逐个插入到这个有序的子序列中去 ，相应的元素要移动。
例：
待排元素序列：[53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序： [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69]
对记录的关键字大小进行比较 将记录从一个位置移动到另一个位置 当待排序记录的关键字均不相同时，则排序结果是唯一 的，否则排序的结果不一定唯一。
排序
4、排序的稳定性
在待排序的文件中，若存在 多个关键字相同的记录，经 过排序后这些具有相同关键 字的记录之间的相对次序保 持不变，该排序方法是稳定 的；
排序
性能分析
在查找循环中用来监视下标变量j是否越界。
R[0] R[1] R[2] 6 20 6 15 6 20 7 6 15 367
36
R[3] R[4] R[5] 15 7 3 15 7 3 20 7 3 15 20 3 7 15 20
直接插入排序的程序：
#include "stdio.h" #define n 5 int ar[n]; int c,t;
例如：下列是一组记录对应的关键字序列
(52, 49, 80, 36, 14, 58, 61, 23, 97, 75) 调整为
(14, 23, 36, 49, 52, 58, 61 ,75, 80, 97)
排序
2. 排序的定义
假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn } 这些关键字相互之间可以进行比较，即在 它们之间存在着这样一个关系 ：
Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为
{ Rp1, Rp2, …，Rpn } 的操作称作排序。
排序
3、排序的基本操作
排序的概念：就是要整理文件中的记录，使之按关键字 递增(或递减)次序排列起来。
排序过程的组成步骤：首先比较两个关键字的大小； 然 后将记录从一个位置移动到另一个位置。
排序
顺序查找、二分查找、二叉树查找以及散列表上查找及 算法思想
排序的基本概念以及选择、插入、交换和归并四类排序 的基本思想和算法
1.4 内部排序
一、基本概念 二、插入排序 三、交换排序 四、选择排序 五、归并排序
排序
一、基本概念
排序
1. 排序的功能：将一个数据元素（或记录） 的任意序列，重新排成一个按关键字有序 的序列。
把新元素（未排序的元素的关键字）逐个插入正在增长 的顺序表中。
寻找插入位置的方法： 线性插入排序 对半插入排序 希尔排序
排序
1、线性插入排序
基本思想：每步将一个待排序的元素按其大小插入到 前面已排序的数据中的适当位置。重复该工作，直至 有序区包含所有元素。
有序序列L.r[1..i-1] 无序序列 L.r[i..n]
若有：
{R1 ,..., Ri,...,Rj,.....} 且关键字：
Ki=Kj
i<>j
排序后：
若具有相同关键字的记录之 { Ri,Rj,.....} 间的相对次序发生变化，则 则称该排序结果具有稳定性。 称5、排序的分类
内部排序：是指在排序的整个过程中，数据全部存放 在计算机的内存储器里，并且在内存储器里调整数据 的位置；
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];
// 插入
}}
排序
哨兵(监视哨)
哨兵(监视哨)有两个作用
作为临时变量存放R[i](当前要进行比较的关键字)的 副本；
