插入排序 线性插入排序的基本思想是:第1遍,将初始文 件中的记录R1看作有序子文件,将R2插入这个 子文件中。若R2的关键字小于R1的关键字,则 R2插在R1的前面,否则R插在R1的后面。第2 遍,将R3插入前面的两个记录的有序子文件中 得到3个记录的有序子文件。依此类推,继续( 进行下去,直到将R插入到前面的n-1个记录的 有序子文件中,最后得到n个记录的有序文件 下一顶
返回本章首页 下一页 上一页 插入排序 线性插入排序的基本思想是：第1遍，将初始文 件中的记录R1看作有序子文件，将R2插入这个 子文件中。若R2的关键字小于R1的关键字，则 R2插在R1的前面，否则R2插在R1的后面。第2 遍，将R3插入前面的两个记录的有序子文件中， 得到3个记录的有序子文件。依此类推，继续 进行下去，直到将Rn插入到前面的n-1个记录的 有序子文件中，最后得到n个记录的有序文件
线性插入排序的基本思想是:第1遍,将 初始文件中的记录R1看作有序子文件, 将R2插入这个子文件中。若R2的关键 字小于R1的关键字,则R2插在R1的前 面,否则R2插在R1的后面。第2遍 将R3插入前面的两个记录的有序子文 件中,得到3个记录的有序子文件 依此类推,继续进行下去,直到将Rn 插入到前面的n1个记录的有序子文 件中,最后得到n个记录的有序文件 KO K1 K2 K3 K4 K5 图9-1所示为线性插入排序的例子。 初始关键字 15 为了避免检测是否应插在R1的前面,在 R1的前面设立记录R,它既是中间变 第一遍排序后:21(2143)89154328 量,又是监视哨。设(R1,R2,… R1)是已排序的有序子文件,则插 第二遍排序后:89(214389)154328 入R的步骤是:首先将R存放到R。中 然后将Ko(即原R的关键字Ki)依 第三遍排序后:15(15214389) 次与K1,K 比较,若K<K (j=1,12,…,1),则R后移 第四遍排序后:43(15214343 个位置,否则停止比较和移动;最后 将R。(即原来待插入的记录R)移到 j+1的位置上。由于R的前面有监视 第五遍排序后:28(1521284343 哨R。,因此不必每次判断下标j是否 出界。算法描述如下 下一顶
返回本章首页 下一页 上一页 线性插入排序的基本思想是：第 1 遍 ， 将 初始文件中的记录 R 1看作有序子文件 ， 将 R 2插入这个子文件中 。 若 R 2的关键 字小于 R 1的关键字 ， 则 R 2插在 R 1的前 面 ，否则 R 2插在 R 1的后面 。 第 2 遍 ， 将 R 3插入前面的两个记录的有序子文 件中 ，得到 3个记录的有序子文件 。 依此类推 ，继续进行下去 ，直到将 R n 插入到前面的 n - 1个记录的有序子文 件中 ，最后得到 n个记录的有序文件 。 图 9 - 1所示为线性插入排序的例子 。 为了避免检测是否应插在 R 1的前面，在 R 1的前面设立记录 R 0，它既是中间变 量，又是监视哨。设（ R 1 ， R 2 ， … ， R i - 1）是已排序的有序子文件，则插 入 R i的步骤是：首先将 R i存放到 R o中， 然后将Ko（即原Ri的关键字Ki）依 次与 K i - 1 ， K i - 2 ， …比较，若 K o<Kj （j=i - 1 ， i - 2 ， … ， 1），则 Rj后移一 个位置，否则停止比较和移动；最后， 将Ro（即原来待插入的记录Ri）移到 j+1的位置上。由于 R i的前面有监视 哨 R o，因此不必每次判断下标j是否 出界。算法描述如下：
void insertsort(struct node rl n+ll,int n 排的为个谁数维排共的决伤圈:中1到为待 i for(i=2; i<=n; i++) *共进行n-1趟* i rol=rl /*r[]为监视哨,也可 做下边循环结束标志* while(rail.key>r[o].key) r[+1]=rj; r[j+1]=r[0j; 下一顶
返回本章首页 下一页 上一页 void insertsort(struct node r[ n+1],int n) /* r[n+1]为一维数组，其中r[0]为监视哨，r[1]到r[n]为待 排序的n个记录，排序好的记录仍放在r中*/ { for(i=2;i<=n;i++) /*共进行n-1趟*/ { r[0]=r[i]; /*r[0]为监视哨，也可 做下边循环结束标志*/ j=i-1; while(r[j].key>r[0].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; } }