1
插入排序的设计、实现、分析与比较
一、 【设计题目】：插入排序的设计、实现、分析与比较
二、 【摘要和关键字】（中文和英文）
摘要：
插入排序可分为直接插入排序，折半插入排序，2-路插入排序，表插入排序，希尔排序。这
里我主要设计分析的是直接插入排序和希尔排序，而其他的，只是随便的说说算法，和一些
可取之处。直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排
好的有序表中。从某些方面来看，直接插入排序的算法简单，就其效率而言，其时间复杂度
为 O（n*n） ，但当待排序记录的数量 n 很小，用的会很好，但当 n 较大时，则不易用此种方
法，那就可以用折半插入排序，2-路插入排序。就折半插入排序而言，它减少了关键字比较
的次数，其复杂度没有变化，而 2-路插入排序 2-路插入排序是在折半插入排序改进得来的，
其目的是减少排序过程中移动记录的次数，但为此需要 n 个记录的辅助空间。最后表插入排
序是一个有序链表。希尔排序，又称缩小增量排序，在时间效率上比以前几种有较大的改进，
下面简单的介绍一下它的思想：在直接插入排序算法中，每次插入一个数，使有序序列只增
加 1 个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）
的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell
于 1959 年在以他名字命名的排序算法中现了这一思想。算法先将要排序的一组数按某个增量
d 分成若干组，每组中记录的下标相差 d.对每组中全部元素进行排序，然后再用一个较小的
增量对它进行，在每组中再进行排序。当增量减到 1 时，整个要排序的数被分成一组，排序
完成。
Inserting to line up preface can is divided in to insert to line up the
preface directly, breaking the half insert to line up the preface,2- the
road inserts to line up the preface, the watch inserts to line up the preface,
hoping the 尔 row preface.Here I the main design analytic inserts to line
up the preface directly with rare row preface, but other, just say the
calculate way literally, with some commendable place.Inserting to line up
directly preface is a kind of most in brief of row preface method, it of
the basic operation is to inserts a record to have lined up to have the
preface form inside goodly.Seeing from some aspects, inserting the
calculate way that line up the preface directly simple, in regard to its
efficiency, its time complicacy a quantity for is O( n* n), but when
treating lining up preface record n is very small, using of would be very
good, but when n is bigger, then using the this kind method not easily,
that can use to break the half insert to line up the preface,2- the road
inserts to line up the preface.In regard to break half insert line up
