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

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

五、归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序适用于子序列有序的数据排序。

1.过程图解

2.算法思想

归并排序是分治法的典型应用。分治法（Divide-and-Conquer）：将原问题划分成 n 个规模较小而结构与原问题相似的子问题；递归地解决这些问题，然后再合并其结果，就得到原问题的解。从上图看分解后的数列很像一个二叉树。

  1. 使用递归将源数列使用二分法分成多个子列

  2. 申请空间将两个子列排序合并然后返回

  3. 将所有子列一步一步合并最后完成排序

3.代码实现

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
def merge_sort(arr):    """归并排序"""    if len(arr) == 1:        return arr    # 使用二分法将数列分两个    mid = len(arr) // 2    left = arr[:mid]    right = arr[mid:]    # 使用递归运算    return marge(merge_sort(left), merge_sort(right))

def marge(left, right):    """排序合并两个数列"""    result = []    # 两个数列都有值    while len(left) > 0 and len(right) > 0:        # 左右两个数列第一个最小放前面        if left[0] <= right[0]:            result.append(left.pop(0))        else:            result.append(right.pop(0))    # 只有一个数列中还有值，直接添加    result += left    result += right    return result

4.算法分析

  1. 比较性：排序时元素之间需要比较，所以为比较排序

  2. 稳定性：我们从代码中可以看到当左边的元素小于等于右边的元素就把左边的排前面，而原本左边的就是在前面，所以相同元素的相对顺序不变，故为稳定排序

  3. 时间复杂度：    复杂度为O(nlog^n)

  4. 空间复杂度：在合并子列时需要申请临时空间，而且空间大小随数列的大小而变化，所以空间复杂度为O(n)

  5. 记忆方法：所谓归并肯定是要先分解，再合并

 
智一面的面试题提供python的测试题
使用地址：python工程师(算法)
http://www.gtalent.cn/exam/interview?token=d61f25fa67a88da0d6ed90d35ab5f1a9