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

我不是女神ヾ 2022-05-19 14:41 284阅读 0赞

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

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

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

![1351471058_8966.jpg][]

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

# 二、插入排序分类 #

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

##     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张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，需自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。
> 
> ![1351472460_1705.jpg][]  
>

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

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

###  ![1351472474_6064.jpg][] ###

> >   
> >

> > **分析过程：**初始时，只有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 的上方

**      **

**        更多"直接插入排序测试"，到《[直接插入排序动画演示][Link 1]》**

> ##    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，排序过程如图。

![1351472518_6384.png][]

> > **执行过程分析：**
> > 
> > **第1趟排序时**，d1=5,整个文件被分成5组：（Tim,Kim,Jim），（Dot,Guy,Kay），（Eva,Amy,Ron）,（Roy,Jon,Jan）,（Tom,Ann）,各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录(及第3个记录)分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图“5-排序后”。
> 
> > **第2趟排序时**，d2=3,整个文件分成3组：（Jim,Jan,Guy,Tom,Ron），（Dot,Ann,Eva,Tim,Roy），（Amy,Kim,Jon,Kay），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个记录分别插入到该组的当前有序区，生成新的有序区；接着依次将第3个记录分别插入到该组当前的有序区，生成新的有序区；完成第4个、第5个记录的插入。
> 
> > **第3趟排序时**，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。
> > 
> >   
> > 
> > 
> > **更多"希尔排序测试"，到《[希尔排序动画演示][Link 2]》**

[1351471058_8966.jpg]: https://img-my.csdn.net/uploads/201210/29/1351471058_8966.jpg
[1351472460_1705.jpg]: https://img-my.csdn.net/uploads/201210/29/1351472460_1705.jpg
[1351472474_6064.jpg]: https://img-my.csdn.net/uploads/201210/29/1351472474_6064.jpg
[Link 1]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/insertsort.htm
[1351472518_6384.png]: https://img-my.csdn.net/uploads/201210/29/1351472518_6384.png
[Link 2]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm