继续我们的简单排序之旅。

题目

看一下这道编程题。

使用python对list中的元素进行插入排序，并编写unittest单元测试用例来进行验证。

插入排序的过程如下图所示。

盯着上面的图看2分钟，把排序的来龙去脉看清楚。

插入排序的过程是

• 首先假设队列左边的元素是已经排序过的元素
• 依次遍历已排序过的元素右边的元素，将该元素与左边已排序的元素做比较，这样左侧已排序的元素个数就会依次增加
• 重复第二步，直到所有的元素全部排序完成

简单来说，插入排序很像是打扑克的理牌过程。我们手里的牌是已经排序过的，每次新抓一张牌，就将牌插入到手里已排序的牌中的合适位置，保证手里的牌一直是排序过的。

参考答案

import unittest

def insertion_sort(arr):
    length = len(arr)
    i = 1 # 从位置1开始向右遍历，因为我们假设位置0上的元素是已经排序好了的
    while i < length: # 开始抓牌
        j = i # j代表当前已排序的数字的结束位置
        while j > 0: # j < 0时证明已经遍历完了已排序的部分
            if arr[j - 1]  > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1] # 找到合适的位置插入
            j = j - 1 # 持续遍历已排序的部分

        i = i + 1 # 持续抓牌

class SortTestCase(unittest.TestCase):

    def test_insertion_sort(self):
        test_data_1 = [8, 7, 6, 5, 4, 0, 1]
        test_data_2 = [9, 5, 2, 7]
        copy_of_data_1 = test_data_1[:]
        copy_of_data_2 = test_data_2[:]

        insertion_sort(test_data_1)
        insertion_sort(test_data_2)
        copy_of_data_1.sort()
        copy_of_data_2.sort()

        self.assertEqual(test_data_1, copy_of_data_1)
        self.assertEqual(test_data_2, copy_of_data_2)


if __name__ == '__main__':
    unittest.main()

思考

大家可以思考下面一些问题

• 插入排序的时间复杂度最好的情况和最坏的情况分别是多少？平均复杂度是多少？