编程笔试题(二)插入排序

乙醇 创建于 8 months 之前

最后更新: less than a minute 之前

阅读数: 464

编程笔试题(二)插入排序

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

题目

看一下这道编程题。

使用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()

思考

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

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

相关课程

mockito简明教程
图文
mockito简明教程

课程分类: 测试工具

mock工具

  • 已完结
  • 已更新7集
  • 最后更新时间: 2024-03-18 12:50:29

免费

查看详情
requests从入门到精通
图文
requests从入门到精通

课程分类: 测试工具 接口测试

python接口测试必会

  • 已完结
  • 已更新16集
  • 最后更新时间: 2024-03-18 12:54:40

免费

查看详情
Locust实用教程
图文
Locust实用教程

课程分类: 性能测试 测试工具

python语言实现的非常出色性能测试工具

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-18 12:24:59

免费

查看详情
TDD测试驱动开发教程
图文
TDD测试驱动开发教程

课程分类: 测试框架 软件测试基础

TDD其实并不神秘

  • 已完结
  • 已更新7集
  • 最后更新时间: 2024-03-18 11:53:22

免费

查看详情
软件测试基础教程
图文
软件测试基础教程

课程分类: 软件测试基础

转码和转行必备

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-18 11:40:05

免费

查看详情
软件测试入门教程
图文
软件测试入门教程

课程分类: 软件测试基础

新人如何转码到软件测试

  • 已完结
  • 已更新9集
  • 最后更新时间: 2024-03-17 11:07:23

免费

查看详情