vlambda博客
学习文章列表

在昨天的文章里面，我们已经知道，可以使用 heapq.merge把两个有序列表合并成新的有序列表。

现在，我们来设计一个排序算法，对列表：[1,4,2,0,4,5,1,-3,-8,188,34] 进行排序。

我们现在先把列表拆分成a列表：[1,4,2,0,4,5]和b列表 [1,-3,-8,188,34]。如果我们能够分别让这两个列表各自有序，然后应用昨天的方法，合并一下，最终结果自然就出来了。

那么如何让这两个列表各自有序呢？我们以 [1,4,2,0,4,5]为例。继续把它拆分为两个列表 [1,4,2]和 [0,4,5]。只要这两个列表各自有序，那么合并一下就行了。

我们再来看 [1,4,2]，如何让它有序呢？我们继续分成两个列表 [1]和 [4,2]。显然只有一个元素的列表 [1]是有序的。

再来看 [4,2]，继续分成两个列表 [4]和 [2]。这两个列表都只有一个元素，所以他们都是有序的。此时对他们进行合并，得到 [2,4]。

[1] 与 [2,4]合并，得到 [1,2,4]。

[1,2,4]与 [0,4,5]合并，得到 [0,1,2,4,4,5]。

[0,1,2,4,4,5]与 [-8,-3,1,34,188]合并，得到 [-8,-3,0,1,1,2,4,4,5,34,188]。

排序完成。

整个过程先拆分再合并，这种排序算法叫做 归并算法。它的时间复杂度始终是 O(nlogn)。而我们常常听说的快速排序，只有在最好的情况下时间复杂度才能达到 O(nlogn)。所以归并排序在时间复杂度这个角度是优于快速排序的。

那么如何使用代码来实现呢？合并的部分请看昨天的文章，今天我们主要描述拆分的逻辑：

 
   
   
 

  
    
    
  
import heapq
  
    
    
  


  
    
    
  
def sort(target):
  
    
    
  
 if not target:
  
    
    
  
 return []
  
    
    
  
 if len(target) == 1:
  
    
    
  
 return target
  
    
    
  
 left = target[:len(target) // 2]
  
    
    
  
 right = target[len(target)//2 :]
  
    
    
  
 sorted_left = sort(left)
  
    
    
  
 sorted_right = sort(right)
  
    
    
  
 result = heapq.merge(sorted_left, sorted_right)
  
    
    
  
 return result
 
   
   
 

运行效果如下图所示：