《算法导论》2.1 节《插入排序》：笔记、代码实现与练习解答
以下是书本展示的插入排序的直译代码：
#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]
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
