智一面的面试题提供python的测试题

使用地址：http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9

一、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，一层一层的将较大的元素往后移动，其现象和气泡在上升过程中慢慢变大类似，故成为冒泡排序。
1.过程图解
2.算法思想
  1. 从第一个和第二个开始比较，如果第一个比第二个大，则交换位置，然后比较第二个和第三个，逐渐往后
  2. 经过第一轮后最大的元素已经排在最后，所以重复上述操作的话第二大的则会排在倒数第二的位置。
  3. 那重复上述操作n-1次即可完成排序，因为最后一次只有一个元素所以不需要比较
  4. 3.代码实现
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    def bubble_sort(arr):    """冒泡排序"""    # 第一层for表示循环的遍数    for i in range(len(arr) - 1):        # 第二层for表示具体比较哪两个元素        for j in range(len(arr) - 1 - i):            if arr[j] > arr[j + 1]:                # 如果前面的大于后面的，则交换这两个元素的位置                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr
    4.算法分析
    冒泡排序是一种简单直接暴力的排序算法，为什么说它暴力？因为每一轮比较可能多个元素移动位置，而元素位置的互换是需要消耗资源的，所以这是一种偏慢的排序算法，仅适用于对于含有较少元素的数列进行排序。
    稳定性：我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置，所以相同元素的相对顺序不可能改变，所以它是稳定排序
    比较性：因为排序时元素之间需要比较，所以是比较排序
    时间复杂度：因为它需要双层循环n*(n-1))，所以平均时间复杂度为O(n^2)
    空间复杂度：只需要常数个辅助单元，所以空间复杂度为O(1)，我们把空间复杂度为O(1)的排序成为原地排序（in-place）
    记忆方法：想象成气泡，一层一层的往上变大
    智一面的面试题提供python的测试题
    使用地址：python工程师(算法)
    http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9