102插入排序 希尔排序( Shells methool)(又称为缩小增量排序) 基本思想:分割成若干个较小的子文件,对各个子文件分别进 行直接插入排序,当文件达到基本有序时,再对整个文件进行一次 直接插入排序。 2.依据:(1)若待排序文件基本有序",即文件中具有特性 r[ ikey<Max{rli}1<记录数较少, 则文件中大多数记录都不需要进行插入。 (2)基本有序时,直接插入排序效率可以提高,接近于O(m)10.2 插入排序 三. 希尔排序（Shell`s Methool）(又称为缩小增量排序) ⒈ 基本思想：分割成若干个较小的子文件，对各个子文件分别进 行直接插入排序，当文件达到基本有序时，再对整个文件进行一次 直接插入排序。 ⒉ 依据：⑴若待排序文件"基本有序" ，即文件中具有特性： r[i].key＜ Max {r[j ]} 1≤j＜i的记录数较少， 则文件中大多数记录都不需要进行插入。 ⑵基本有序时，直接插入排序效率可以提高，接近于O(n)