# 编程笔试题(一)冒泡排序 最近了解到很多测试同学在面试做笔试题的时候都会遇到编程题，总的看来测试同学的编程题都不是很困难，主要在考察大家的代码基本功，一般以简单的算法为主。这里就给大家介绍一些最基本的算法，希望对大家的面试有一些帮助。 在阅读文章之前，希望大家有这样的一些知识积累。 * 能看懂简单的python代码 * 能写一些简单的python代码并运行起来 * 知道python的一些简单数据结构，比如list 基本算法里总是离不开排序。所谓的排序就是把一组乱序的数据从大到小或者从小到大的排列出来。 比如一组数字，9，5，2，7，我们按照生序排列的结果就是2,5,7,9。 ### 题目 首先看这道编程题。 > 使用python对list中的元素进行冒泡排序，并编写unittest单元测试用例来进行验证。 排序算法里最简单的就是冒泡排序。冒牌排序的过程用下面这张图来解释是最合适不过了。 ![http://img.testclass.net/Bubble-sort-example-300px.gif] 盯着上面的图看2分钟，把排序的来龙去脉看清楚。 从上面的图里我们可以知道 * 首先比较每个相邻的元素，把大的元素换到右边，这样每次比较完一行就可以把最大的数字移动到最右边，这就是所谓的冒泡了 * 重复上面的过程，把每次找到的最大的元素换到当前比较队列的最右 这样一来当所有的循环完成之后排序就自然完成了。 下面就是代码实现了。实现代码的时候我们需要先想明白代码运行的次数。 我们可以把冒泡排序分成2个小的任务,假设有n个数字需要排序 * A: 找到当前未排序的数字中最大的数字，将其移动到未排序数字的最右边，具体做法遍历当前未排序的数字，将该数字与右边的数字进行比较 * B: 循环n次A 对于B来说，循环次数很明确了，就是n次。对于A来说，第1次循环的最后应该是比较第n-1与第n个元素，如果有比较就进行移动，第2次循环是比较第n-2个元素和第n-1个元素，因为第n个元素是**当前最大的已经排序的元素了**，所以没有必要与第n个元素进行比较。依次类推可知A其实就是从n-1开始，到1结束。 这里其实有2个变量控制循环逻辑 * 未排序元素的结束位置，A使用 * 已经找到的最大元素的个数, B使用 ### 参考答案 ```python import unittest def bubble_sort(arr): length = len(arr) for i in range(length): # i 就是当前已经找到的最大元素个数，从0开始，表示找到了0到n个 for j in range(length - i - 1): # 任务A的具体实现，每次循环的结束点都是比较当前未排序元素的倒数第2个和最后1个 if arr[j] > arr[j + 1]: arr[j], arr[j+1] = arr[j+1], arr[j] # python中交换变量值的语法糖，面试里这样写大概能加分把 # tmp = arr[j] 这样交换也可以，不过没有上面写法显得老练 # arr[j] = arr[j+1] # arr[j+1] = tmp class SortTestCase(unittest.TestCase): def test_bubble_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[:] # 拷贝test_data_1 copy_of_data_2 = test_data_2[:] # 拷贝test_data_2 bubble_sort(test_data_1) bubble_sort(test_data_2) copy_of_data_1.sort() # 把copy_of_data_1进行排序 copy_of_data_2.sort() # 把copy_of_data_2进行排序 self.assertEqual(test_data_1, copy_of_data_1) self.assertEqual(test_data_2, copy_of_data_2) if __name__ == '__main__': unittest.main() ``` ### 思考 大家可以思考下面一些问题 * 上面是算法的时间复杂度和空间复杂度? * 冒泡排序的时间复杂度最好的情况和最坏的情况分别是多少？平均复杂度是多少？ 原始封面 ![课程图片](https://images.unsplash.com/photo-1484402628941-0bb40fc029e7?w=300)