Python之归并排序

小鱼儿 2022-02-20 08:49 241阅读 0赞

**归并排序：**  
是一种递归算法，它持续地将一个列表平均分成两半。如果列表是空的或者只有一个元素，那么它就被排好了(最基本情况)。如果列表里的元素超过一个，就把列表继续拆分，然后再分别对两个部分调用递归排序。一旦这两个部分都排好了，那么就把这两个列表结合在一起，组成一个有序的新列表。

归并排序使用分而治之的策略，其时间复杂度为O(nlogn)。

**示例：**

# 将左右子列表按升序依次合并为一个新列表
    def merge(left, right):
    	result = []									#初始化合并后的新列表为空
    	while left and right:						#左右子列表均不为空时循环
    		# 下面将左右子列表中的元素按从小到大的顺序依次添加到新列表中。使用例子更易理解。
    		if left[0] < right[0]:
    			result.append(left.pop(0))			#将小的先添加到新列表
    		else:
    			result.append(right.pop(0))			#将小的先添加到新列表
    	if left:									#若左子列表不为空，右子列表为空，则
    		result += left 							#更新新列表为新列表加左子列表
    	if right:									#若右子列表不为空，左子列表为空，则
    		result += right 						#更新新列表为新列表加右子列表
    	return result
    
    # 将指定列表递归分隔成多个空或只有一个元素的列表
    def mergeSort(alist):
    	if len(alist) < 2:							#若列表为空或只有一个元素，则
    		return alist 							#直接返回列表
    	else:										#若列表元素超过一个，则
    		n = len(alist) // 2 					#平分，若不能平分则差1个，不影响
    		left = alist[:n] 						#左侧子列表
    		right = alist[n:]						#右侧子列表
    		left = mergeSort(left)					#递归，直至最小列表为空或只有一个元素
    		right = mergeSort(right) 				
    	return merge(left, right)					#合并子列表
    
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(mergeSort(alist))

**结果为：**

[17, 20, 26, 31, 44, 54, 55, 77, 93]