102插入排序 插入排序的基本方法是 将待排序文件中的记录,逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 10.21直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第个记录R进 插入时,R1,R2,…,R1已排序,将记录R的排序码 key;与已经排好序的排序码从右向左依次比较,找到R 应插入的位置,将该位置以后直到R1各记录顺序后移, 空出该位置让R插入
组记录的排序码分别为: 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
需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时 [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨
void insertsort(table*tab) for(i=2;i<=tab-> length;+)依次插入从第2个开始的所有元素 tab->[0]key=tab->r[].key;/设置哨兵,准备找插入位置 while(tab->ro]key<tab->]key)找插入位置并后移*/ tab->r+1]key=tab->]key;/后移* 1; 继续向前(左)查找 tab->+1key=tab->r0]key;/插入第个元素的副本,即前面设置的哨兵* 算法10.1直接插入排序算法