算法之9 | 插入排序（算法之9+|+插入排序顺序）

插入排序是最简单的一种排序算法，它的伪代码如下：

　　代码2.1-1：插入排序

　　// 参数 A：待排序的数组

　　INSERTION-SORT(A)

　　　　for j = 2 to A.length

　　　　key = A[j]

　　　　// Insert A[j] into the sorted sequence A[1..j-1]

　　　　i = j-1

　　　　while i > 0 and A[i] > key

　　　　　　A[i+1] = A[i]

　　　　　　i = i-1

　　　　A[i+1] = key

说明INSERTION-SORT在数组

上的执行过程。

解

重写过程INSERTION-SORT，使之按非升序（而不是非降序）排序。

解

　　代码2.1-2：非升序插入排序

　　// 参数 A：待排序的数组

　　REVERSE-INSERTION-SORT(A)

　　　　for j = 2 to A.length

　　　　key = A[j]

　　　　// Insert A[j] into the sorted sequence A[1..j-1]

　　　　i = j-1

　　　　while i > 0 and A[i] < key

　　　　　　A[i+1] = A[i]

　　　　　　i = i-1

　　　　A[i+1] = key

考虑以下查找问题：
　　输入：

个数的一个序列

和一个值

。

　　输出：下标

使得

或者当

不在

中出现时，

为特殊值

。

　　写出线性查找的伪代码，它扫描整个序列来查找

。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

解

　　代码2.1-3：线性查找

　　// 参数 A：一个数组

　　// 参数 v：需要查找的值

　　LINEAR-SEARCH(A, v)

　　　　for i = 1 to A.length

　　　　　　if A[i] == v

　　　　　　　　return i

　　　　return NIL

考虑把两个

位二进制整数加起来的问题，这两个整数分别存储在两个

元数组

和

中。这两个整数的和应按二进制形式存储在一个

元数组

中。请给出该问题的形式化描述，并写出伪代码。

解

　　代码2.1-4：二进制整数相加

　　// 参数 A和B：表示两个二进制整数的数组，数组中的元素只能是0或1

　　// 参数 n：输入数组的长度

　　// 参数 v：需要查找的值

　　BINARY-ADD(A, B, n)

　　　　create a new array C[1..n+1]

　　　　carry = 0

　　　　for i = 1 to n

　　　　　　sum = A[i] + B[i] + carry

　　　　　　if sum < 2

　　　　　　　　C[i] = sum

　　　　　　　　carry = 0

　　　　　　else

　　　　　　　　C[i] = sum - 2

　　　　　　　　carry = 1

　　　　C[n+1] = carry

插入排序的算法分析

算法分析的一些概念

• 算法运行时间：在特定的输入下，所执行的基本操作数（步数），这是假设每次原子操作所花费的时间都是常量c，那么，如果执行一条语句需要n步，每步视为一个原子操作，那么，这条语句所花费时间为t = cn，那么运行总时间，则是对每对cn的值求和。
• 算法的性能：算法的性能，取决于给定规模的输入，同时，一个算法的运行时间还依赖于给定的是该规模下的那种输入。
• 数学的一些概概念：弃低阶项，如an^2+bn+c可以变为n^2

插入排序算法分析

那么，算法分析通常会出现，最佳情况、平均情况（期望）、最坏情况。其中最佳情况（实际中不存在）、平均情况（需要通过数学的方法建立相应场景）、最坏情况（最具参考价值）。

插入排序的base-case（最佳情况）：如果是已排序好的，将会出现最佳情况

在该情况下T(n) = an + b

插入排序的worst-case（最坏情况）：待排序数组为逆序，将出现最坏情况

在该情况下T(n) = an^2+bn+c

总结下，插入排序的最佳时间复杂度为T(n) = n，最坏复杂时间为T(n) =n^2

worst-case的参考价值：

• 一个算法的最坏运行情况运行时间是在任何输入下运行时间的一个上界
• 对于某些算法来说，最坏情况出现得还是相当频繁的。如，在数据库中检索一条信息时，当要找到的信息不在数据库中时，检索算法的最坏情况就会经常出现。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。