enter image description here

插入排序法是一种很容易想到的算法,它的思路与打扑克时排列手牌的方法很相似。比如我们现在单手拿牌,然后要将牌从左至右、由小到大进行排序。此时我们需要将牌一张张抽出来,分别插入到前面已排好序的手牌中的适当位置。重复这一操作直到插入最后一张牌,整个排序就完成了。

插入排序法的算法如下。

1 insertionSort(A, N) // 包含N 个元素的0 起点数组A

2 for i 从1 到N-1

3 v = A[i]

4 j = i - 1

5 while j >= 0 且 A[j] > v

6 A[j+1] = A[j]

7 j--

8 A[j+1] = v

请编写一个程序,用插入排序法将包含N 个元素的数列A 按升序排列。程序中需包含上述伪代码所表示的算法。为检验算法的执行过程,请输出各计算步骤的数组(完成输入后的数组,以及每次i 自增后的数组)。

输入 在第1 行输入定义数组长度的整数N。在第2 行输入N 个整数,以空格隔开。

输出  输出总共有N 行。插入排序法每个计算步骤的中间结果各占用1 行。数列的各元素之间空1 个空格。请注意,行尾元素后的空格等多余的空格和换行会被认定为Presentation Error。

限制 1≤N≤100

0 ≤ A 的元素≤ 1000

enter image description here

答案不正确时的注意点

  • 数组长度是否足够长
  • 是否搞错了0 起点和1 起点的数组下标
  • 是否误用了循环变量(比如i、j)
  • 是否输出了多余的空格或换行

讲解

如图3.1 所示,插入排序法在排序过程中,会将整个数组分成“已排序部分”和“未排序部分”。

enter image description here

插入排序法

  • 将开头元素视作已排序
  • 执行下述处理,直至未排序部分消失

    1. 取出未排序部分的开头元素赋给变量v。

    2. 在已排序部分,将所有比v 大的元素向后移动一个单位。

    3. 将已取出的元素v 插入空位。

举个例子,我们对数组A={8, 3, 1, 5, 2, 1} 进行插入排序时,整体流程如图3.2 所示。

enter image description here

在步骤1 中,将开头元素A0 视为已排序,所以我们取出A1 的3,将其插入已排序部分的恰当位置。首先把原先位于A[0] 的8 移动至A1,再把3 插入A[0]。这样一来,开头2 个元素就完成了排序。

在步骤2 中,我们要把A2 的1 插入恰当位置。这里首先将比1 大的A1 和A0顺次向后移一个位置,然后把1 插入A[0]。

在步骤3 中,我们要把A3 的5 插入恰当位置。这次将比5 大的A2 向后移一个位置,然后把5 插入A2

之后同理,将已排序部分的其中一段向后移动,再把未排序部分的开头元素插入已排序部分的恰当位置。插入排序法的特点在于,只要0 到第i 号元素全部排入已排序部分,那么无论后面如何插入,这个0 到第i 号的元素都将永远保持排序完毕的状态。

实现插入排序法时需要的主要变量如图3.3 所示。

enter image description here

外层循环的i 从1 开始自增。在每次循环开始时,将A[i] 的值临时保存在变量v 中。

接下来是内部循环。我们要从已排序部分找出比v 大的元素并让它们顺次后移一个位置。这里,我们让j 从i-1 开始向前自减,同时将比v 大的元素从A[j] 移动到A[j+1]。一旦j 等于-1 或当前A[j] 小于等于v 则结束循环,并将v 插入当前j+1 的位置。

考察

在插入排序法中,我们只将比v(取出的值)大的元素向后平移,不相邻的元素不会直接交换位置,因此整个排序算法十分稳定。

然后我们考虑一下插入排序法的复杂度。这里需要估算每个i 循环中A[j] 元素向后移动的次数。最坏的情况下,每个i 循环都需要执行i 次移动,总共需要1+2+…+N-1=(N²-N)/2次移动,即算法复杂度为O(N²)。大多数时候,我们在计算复杂度的过程中,可以大致估计一下运算次数,然后只留下对代数式影响最大的项,忽略常数项。比如 enter image description here,这里的N 相对于N² 而言就小得足以忽略,然后再忽略掉常数倍 enter image description here,得出复杂度与N² 成正比。当然,前提是假设这里的N 足够大。

插入排序法是一种很有趣的算法,输入数据的顺序能大幅影响它的复杂度。我们前面说它的复杂度为O(N²),也仅是指输入数据为降序排列的情况。如果输入数据为升序排列,那么A[j] 从头至尾都不需要移动,程序只需要经历N 次比较便可执行完毕。可见,插入排序法的优势就在于能快速处理相对有序的数据。

参考答案

enter image description here

评论

推荐 0
从分析角度来看,插入排序和冒泡排序的处理上都是将整个待处理数组分成“待排序”和“已排序”两个部分。插入排序依次比较-挪位-插入;冒泡排序相邻进行比较-换位。

我要评论

需要登录后才能发言
登录未成功,请修改提交。