102插入排序 插入排序的基本方法是: 将待排序文件中的记录,逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 1021直接插入排序 直接插入排序算法的思路是初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第论个记录R进行 插入时,R1,R2…,R已排序,将记录R的排序码 key与已经排好序的排序码从右向左依次比较,找到R 应插入的位置,将该位置以后直到R各记录顺序后移 空出该位置让R插入
10.2 插入排序 插入排序的基本方法是: 将待排序文件中的记录， 逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置，并保持新文件有序。 10.2.1 直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序，然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第i个记录Ri进行 插入时，R1，R2，…，Ri-1已排序，将记录Ri的排序码 keyi与已经排好序的排序码从右向左依次比较，找到Ri 应插入的位置，将该位置以后直到Ri-1各记录顺序后移， 空出该位置让Ri插入
组记录的排序码分别为 312,126,272,226,28,165,123 初始时将第1个排序码作为已经排好序的,把排好序 的数据记录放入中括号[中,表示有序的文件,剩下 的在中括号外,如下所示 312],126,272,226,28,165,123 设前3个记录的排序码已重新排列有序,构成一个含 有3个记录的有序文件 [126,272,312],226,28,165,123 现在要将第4个排序码226插入
一组记录的排序码分别为: 312，126，272，226，28，165，123 初始时将第1个排序码作为已经排好序的，把排好序 的数据记录放入中括号[]中，表示有序的文件，剩下 的在中括号外，如下所示： [312]，126，272，226，28，165，123 设前3个记录的排序码已重新排列有序，构成一个含 有3个记录的有序文件: [126，272，312]，226，28，165，123 现在要将第4个排序码226插入 ！
[126,272,312],226,28,165,123 现在要将第4个排序码226插入 将待插入的排序码226和已经有序的最后一个排 序码312比较,因为待插入的排序码226小于312,所 以226肯定要置于312的前面,至于是否就是置于312 的前一个位置,此时还不能确定,需要继续向左比较; 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置,在空出的位置插入待 排序的排序码226,得一含有4个记录的有序文件 [126,226,272,312],28,165,123
[126，272，312]，226，28，165，123 现在要将第4个排序码226插入 ！ 将待插入的排序码226和已经有序的最后一个排 序码312比较，因为待插入的排序码226小于312，所 以226肯定要置于312的前面，至于是否就是置于312 的前一个位置，此时还不能确定，需要继续向左比较； 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置，在空出的位置插入待 排序的排序码226，得一含有4个记录的有序文件： [126，226，272，312]，28，165，123
需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时 [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨
需要注意的是，当待插入排序码小于所有已排序的 排序码时，如在插入第5个值28时： [126，226，272，312]，28，165，123 算法设计的时候如处理？ 方法之一：设置“哨 兵
void insertsort(table*tab for(i=2;<=tab-> length; i++)/依次插入从第2个开始的所有元素 {j=i-1; tab->r[0]key=tab→>]key/设置哨兵,准备找插入位置 While(tab->r0]key<tab->rj]key)找插入位置并后移 tab->j+1]key=tab->key;/后移 继续向前(左)查找* tab->rj+1]key=tab->ro]key;/插入第个元素的副本,即前面设置的哨兵 算法10.1直接插入排序算法
void insertsort(table *tab) { int i,j; for(i=2;i<=tab->length;i++)/*依次插入从第2个开始的所有元素*/ { j=i-1; tab->r[0].key=tab->r[i].key;/*设置哨兵，准备找插入位置*/ while(tab->r[0].key<tab->r[j].key) /*找插入位置并后移*/ { tab->r[j+1].key=tab->r[j].key; /*后移*/ j=j-1; /*继续向前（左）查找*/ } tab->r[j+1].key=tab->r[0].key; /*插入第i个元素的副本，即前面设置的哨兵*/ } } 算法10.1 直接插入排序算法