图解"数据结构--内部排序算法"----插入排序：直接插入排序、希尔排序

一、插入排序(Insertion Sort)的基本思想

我的理解：把要排序的记录插入到已排好序的文件中。

标准定义：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的字文件中的恰当位置，直到全部记录插入完成为止。

第一个记录为有序区，依次将剩余记录插入其中。

二、插入排序分类

本文介绍两种插入排序方法：直接插入排序和希尔排序。

2.1 直接插入排序 2.1.1 直接插入排序实现思路

插入排序就是先有一个有序的数据区，然后把要插入的数据插到指定的位置；而排序首先给的就是无序的，我们怎么确定先得到一个有序的数据呢？答案就是：如果只有一个记录，当然是有序的咯。我们先从无序区拿第一个记录出来，他是有序的，然后把无序区中的记录一个一个插入到其中，那么插入之后是有序的，所以直到最后都是有序的。。哈哈。结果就出来了！

2.1.2 直接插入排序实现过程

假设待排序的记录存放在数组R[1..n]中，排序过程的某一中间时刻，R被分成两个子区间R[1..i-1]和R[i..n]，其中：前一个子区间是已排好序的有序区；后一个子区间则是无序区(当前未排序的部分)。直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区R[1..i-1]中适当的位置上，使R[1..i]变为 有序区。

直接插入排序的方法通常称为增量法，因为它每次使有序区增加1个记录。

插入排序与我们打扑克时整理手上的牌非常类似：摸来的第1张牌无需整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，需自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

2.1.3 举例说明"直接插入排序的排序过程"

下图，展示了对4个元素（4,3,1,2）直接插入排序的过程。

分析过程：初始时，只有1个记录’4’，自然有序；无序区为(3,1,2).

我们只需把(3,1,2)依次插入当前的有序区中。

(a) 将‘3’插入到’4’组成的有序区中

3 与4做比较，3<4,所以，3在4 的上方

(b) 将‘1’插入到’34’组成的有序区中

1 与有序区中的34做比较，1<3,所以，1在3 的上方

(c) 将‘2’插入到’134’组成的有序区中

2与有序区中的134做比较，1<2<3,所以，2在3 的上方

更多"直接插入排序测试"，到《直接插入排序动画演示》

2.2 希尔排序

2.2.1 希尔排序(Shell Sort)基本思想

先取定一个小于n的整数d1 作为第1个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第2个增量d2< d1重复上述的分组和排序，直至所取的增量d1=1(dt< dt-1<…< d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

注意：1.各组的划分不是简单地逐段划分；

2. 增量的选择以及排序最终以1为增量进行排序结束；

3.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

2.2.2 举例说明"希尔排序的排序过程"

假设待排序文件有14个记录，其关键字分别为：Tim,Dot,Eva,Roy,Tom,Kim,Guy,Amy,Jon,Ann,Jim,Kay,Ron,Jan.增量序列的取值依次是：5,3,1，排序过程如图。

执行过程分析：

第1趟排序时，d1=5,整个文件被分成5组：（Tim,Kim,Jim），—ot,Guy,Kay），（Eva,Amy,Ron）,（Roy,Jon,Jan）,（Tom,Ann）,各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录(及第3个记录)分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图“5-排序后”。

第2趟排序时，d2=3,整个文件分成3组：（Jim,Jan,Guy,Tom,Ron），—ot,Ann,Eva,Tim,Roy），（Amy,Kim,Jon,Kay），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个记录分别插入到该组的当前有序区，生成新的有序区；接着依次将第3个记录分别插入到该组当前的有序区，生成新的有序区；完成第4个、第5个记录的插入。

第3趟排序时，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。

更多"希尔排序测试"，到《希尔排序动画演示》