编程笔试题(二)插入排序
乙醇 创建于 8 months 之前
最后更新: less than a minute 之前
阅读数: 523
继续我们的简单排序之旅。
题目
看一下这道编程题。
使用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()
思考
大家可以思考下面一些问题
- 插入排序的时间复杂度最好的情况和最坏的情况分别是多少?平均复杂度是多少?