《算法导论》2.1 节《插入排序》：笔记、代码实现与练习解答¶
笔记¶
较为低效的排序算法，只在元素较少时有效。
算法的最坏情况输入为降序排列的元素，比如
[7, 6, 5, 4, 3, 2, 1]，每次移动元素的复杂度为 O(N) ，因此算法的复杂度为 O(N^2) 。原地排序，执行时只需要常量大小的额外内存空间。
每次排序 A[i] 的时候， A[i] 之前的元素都是有序的，而算法要做的就是将 A[i] 添加到这个有序数组当中，并把它放到合适的位置上。
代码实现¶
以下是书本展示的插入排序的直译代码：
#coding:utf-8
def insertion_sort(array):
for i in range(1, len(array)): # 产生一个 1..array.length 的序列
key = array[i] # 获取被排序的键
j = i-1 # 将被排序的键与排在它前面的数组元素进行比较
while j >= 0 and array[j] > key: # 如果排在前面的元素有比被排序键更大的元素
array[j+1] = array[j] # 那么将这些元素移动到数组靠后的位置
j -= 1 # 一直执行以上操作，直到发现比被排序键更小的元素为止
array[j+1] = key # 最后将被排序键放到它应该在的位置上
if __name__ == "__main__":
import random
array = list(range(7))
random.shuffle(array)
print("input = {0}".format(array))
insertion_sort(array)
print("output = {0}".format(array))
有两个要注意的地方：
书本原来在外循环使用
j作下标， 内循环使用i作下标， 这里我根据自己的习惯进行了修改， 与书本的做法正好相反。书本的数组下标是以
1为开始的， 而 Python 的数组下标则是以0为开始， 所以书本中的for j = 2 to A.length在代码中改成了for i in range(1, len(array))。跟理由 2 一样， 书本中的
while i > 0 and ...在代码中改成了while j >= 0 and ...。 刚开始时没有注意到这个问题， 结果在测试的时候发现数组的第一个元素没有被排序， 吓我一跳， 以为书本的算法出 bug 了。
测试结果：
$ python3 insertion_sort.py
input = [0, 5, 4, 3, 1, 2, 6]
output = [0, 1, 2, 3, 4, 5, 6]
练习解答¶
2.1-1¶
使用插入排序对输入 [31, 41, 59, 26, 41, 58] 进行排序的过程：
1）排序 A[1] ，值 41
[31, 41, 59, 26, 41, 58]
^
|
31 > 41 为假，直接插入原位
2）排序 A[2] ，值 59
[31, 41, 59, 26, 41, 58]
^
|
41 > 59 为假，直接插入原位
3）排序 A[3] ，值 26
[31, 41, 59, 26, 41, 58]
^ ^
| |
+--+
59 > 26 ，向后移动 59
[31, 41, 59, 59, 41, 58]
^ ^
| |
+---+
41 > 26 ，向后移动 41
[31, 41, 41, 59, 41, 58]
^ ^
| |
+---+
31 > 26 ，向后移动 31
[31, 31, 41, 59, 41, 58]
^
|
已到达 A[0] ，将 26 插入到 A[0]
[26, 31, 41, 59, 41, 58]
4）排序 A[4] ，值 41
[26, 31, 41, 59, 41, 58]
^ ^
| |
+----+
59 > 41 ，向后移动 59
[26, 31, 41, 59, 59, 58]
^
|
41 > 41 为假，无需再移动，将 41 插入到 A[3]
[26, 31, 41, 41, 59, 58]
5）排序 A[5] ，值 58
[26, 31, 41, 41, 59, 58]
^ ^
| |
+---+
59 > 58 ，向后移动 59
[26, 31, 41, 41, 59, 59]
^
|
41 > 58 为假，无需再移动，将 58 插入到 A[4]
[26, 31, 41, 41, 58, 59]
6）排序完毕，结果为 [26, 31, 41, 41, 58, 59] 。
2.1-2¶
题目的要求是写一个产生降序排列结果的插入排序。
比如说，
对于输入 [5, 2, 4, 6, 1, 3] ，
这个降序插入排序应该产生结果 [6, 5, 4, 3, 2, 1] ，
而不是原来的 [1, 2, 3, 4, 5, 6] 。
原来的升序排列插入排序的做法是将较小的值插入到数组的前面， 为了产生一个降序排列的结果， 我们的排序算法应该反其道而行之， 将较大的值插入到数组的前面。
以下是算法的具体实现：
#coding:utf-8
def insertion_sort(array):
for i in range(1, len(array)):
key = array[i]
j = i-1
while j >= 0 and array[j] < key: # 将原来的 array[j] > key 改为 array[j] < key
array[j+1] = array[j]
j -= 1
array[j+1] = key
if __name__ == "__main__":
import random
array = list(range(7))
random.shuffle(array)
print("input = {0}".format(array))
insertion_sort(array)
print("output = {0}".format(array))
这个算法和之前的升序排列的插入算法的唯一不同，
就是将原来的 while j >= 0 and array[j] > key 改成了 while j >= 0 and array[j] < key ，
使得较大的值会被插入到数组的前面。
除此之外，
这个算法跟之前展示的升序插入排序算法没有什么不同。
测试结果：
$ python3 decrease_insertion_sort.py
input = [1, 0, 5, 4, 2, 3, 6]
output = [6, 5, 4, 3, 2, 1, 0]
2.1-3¶
首先， 这道题的输出描述应该有误： “下标 i 使得……， v 为特殊值 NIL”： 这里的“v 为特殊值 NIL”应该改为“i 为特殊值 NIL”才对 —— 将输入值设置为 NIL 是没有意义的， 不知道这是原书错误还是翻译错误。
另外这道问题还有一个不严谨的地方，
那就是，
它没有定义当数组里面出现多个 v 时，
算法应该返回哪个 v 的 i ：
比如对于输入 [1, 3, 5, 2, 3] ，
如果 v=3 ，
那么 i 可以是 1 也可以是 4 。
为了消除这一点，
我的算法实现将会返回第一个遇到的 v 的 i 。
算法实现：
#coding:utf-8
def search_value(array, value):
i = None
for j in range(len(array)):
if array[j] == value:
i = j
break
return i
if __name__ == "__main__":
import random
array = list(range(6))
random.shuffle(array)
value1 = random.choice(array)
value2 = 10086
print("find {0} in {1}, i = {2}.".format(value1, array, search_value(array, value1)))
print("find {0} in {1}, i = {2}.".format(value2, array, search_value(array, value2)))
测试：
$ python3 search_value.py
find 1 in [2, 5, 3, 4, 1, 0], i = 4.
find 10086 in [2, 5, 3, 4, 1, 0], i = None.
（不太规范、非常随意的）循环不变式证明：
初始化： 在第一次循环之前，
array[0]要么等于value， 要么不等于value： 对于前者， 算法会返回0； 而对于后者， 算法将在后续的循环中继续进行查找。保持： 算法在第
i次循环时， 会检查array[i]是否等于value， 是的话就返回i， 不是的话就继续进行下次循环。终止： 当算法找到
array[i] == value时， 它会终止循环， 并返回i； 如果算法遍历了整个数组也没有找到value所在的i， 那么算法返回None。
2.1-4¶
TODO