8

《算法导论》2.1 节《插入排序》：笔记、代码实现与练习解答 — blog.huangz.me

 3 years ago
source link: https://blog.huangz.me/diary/2016/introduction-to-algorithms/section-2-1.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK