归并排序

• 算法思想：
  
  归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

•  1 [54, 26, 93, 17, 77, 31, 44, 55]  #升序排序
   2 #分解  n//2
   3 # [54, 26, 93, 17]   [77, 31, 44, 55]
   4 #
   5 # [54, 26]  [93, 17]   [77, 31]  [44, 55]
   6 #
   7 # [54]  [26]  [93] [17]   [77]  [31]  [44] [55]
   8 
   9 #合并
  10 # [26,54] [17,93] [31,77] [44,55]
  11 #
  12 # [17,26,(54,1),93]   [31,44,(54,2),55,77]
  13 #
  14 # [17,26,31,44,54,55,77,93]
  15 
  16 def merg_sort(alist):
  17     #分解
  18     n=len(alist)
  19     #递归的出口 分解到最小
  20     if n<=1:
  21         return alist
  22     mid=n//2
  23     left_li=merg_sort(alist[0:mid])
  24     right_li=merg_sort(alist[mid:])
  25 
  26     #合并
  27     #排序结果列表
  28     result=[]
  29     left_pointer,right_pointer=0,0
  30     while left_pointer<len(left_li) and right_pointer<len(right_li):
  31         if left_li[left_pointer] <=right_li[right_pointer]:
  32             result.append(left_li[left_pointer])
  33             left_pointer += 1
  34         else:
  35             result.append(right_li[right_pointer])
  36             right_pointer += 1
  37 
  38     #退出循环后，将不为空的列表剩余元素添加到result中
  39     # result+=left_li[left_pointer:]
  40     result.extend(left_li[left_pointer:])
  41     result+=right_li[right_pointer:]
  42 
  43     #将最后排序的结果列表返回
  44     return result
  48 if __name__ ==‘__main__‘:
  49     alist=[54, 26, 93, 17, 77, 31, 44, 55]
  50     print(‘原来的数组：‘)
  51     print(alist)
  52     result=merg_sort(alist)
  53     print(‘排序后：‘)
  54     print(result)

  1 原来的数组：
  2 [54, 26, 93, 17, 77, 31, 44, 55]
  3 排序后：
  4 [17, 26, 31, 44, 54, 55, 77, 93]

   

归并排序

原文：https://www.cnblogs.com/monsterhy123/p/12728835.html