《算法导论》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))

有两个要注意的地方:

  1. 书本原来在外循环使用 j 作下标, 内循环使用 i 作下标, 这里我根据自己的习惯进行了修改, 与书本的做法正好相反。
  2. 书本的数组下标是以 1 为开始的, 而 Python 的数组下标则是以 0 为开始, 所以书本中的 for j = 2 to A.length 在代码中改成了 for i in range(1, len(array))
  3. 跟理由 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.

(不太规范、非常随意的)循环不变式证明:

  1. 初始化: 在第一次循环之前, array[0] 要么等于 value , 要么不等于 value : 对于前者, 算法会返回 0 ; 而对于后者, 算法将在后续的循环中继续进行查找。
  2. 保持: 算法在第 i 次循环时, 会检查 array[i] 是否等于 value , 是的话就返回 i , 不是的话就继续进行下次循环。
  3. 终止: 当算法找到 array[i] == value 时, 它会终止循环, 并返回 i ; 如果算法遍历了整个数组也没有找到 value 所在的 i , 那么算法返回 None

2.1-4

TODO

留言

comments powered by Disqus