6.6归并排序（python数据结构与算法）

亦凉 2021-05-12 11:50 440阅读 0赞

**归并排序**是采用分治法的一个非常典型的应用。归并排序的思想就是先**递归**分解数组，再合并数组时进行排序。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的**指针**就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

## 归并排序的分析 ##

*  实现过程：

![在这里插入图片描述][20200711201414403.gif]

#### 实现： ####

def merge_sort(alist):
        """归并排序"""
        n = len(alist)
        if n <= 1:
            return alist
        mid = n//2
        # 递归调用
        left_sort_list = merge_sort(alist[:mid])
        right_sort_list = merge_sort(alist[mid:])
    
        # 将分开的左右两个list各自排好序
        left_pointer = 0
        right_pointer = 0
        sorted_list = []
    
        while left_pointer < len(left_sort_list) and right_pointer < len(right_sort_list):
            if left_sort_list[left_pointer] < right_sort_list[right_pointer]:
                sorted_list.append(left_sort_list[left_pointer])
                left_pointer += 1
            else:
                sorted_list.append(right_sort_list[right_pointer])
                right_pointer += 1
    
        sorted_list += left_sort_list[left_pointer:]
        sorted_list += right_sort_list[right_pointer:]
    
        return sorted_list
    
    if __name__ == "__main__":
        alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(alist)
        sorted_list = merge_sort(alist)
        print(sorted_list)

### 时间复杂度 ###

*  最优时间复杂度：O( n l o g n nlogn nlogn)
 *  最坏时间复杂度：O( n l o g n nlogn nlogn)
 *  稳定性：稳定  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]

[20200711201414403.gif]: /images/20210511/13b5a983b051494fad4753563f702da1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]: /images/20210511/677fcd79f2fe4100ba46ed4e5ff1b5a8.png