Python：22归并排序

约定不等于承诺〃 2023-05-28 11:18 105阅读 0赞

## 归并排序（Merge sort，或mergesort） ##

## 创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 ##

**分治法:**

*  分割：递归地把当前序列平均分割成两半。
 *  集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

![aHR0cHM6Ly93d3cucnVub29iLmNvbS93cC1jb250ZW50L3VwbG9hZHMvMjAxOS8wMy9tZXJnZVNvcnQuZ2lm][]

代码献上：

> def merge(arr, l, m, r):  
>     n1 = m - l + 1  
>     n2 = r - m
> 
>     \# 创建临时数组  
>     L = \[0\] \* (n1)  
>     R = \[0\] \* (n2)
> 
>     \# 拷贝数据到临时数组 arrays L\[\] 和 R\[\]  
>     for i in range(0, n1):  
>         L\[i\] = arr\[l + i\]
> 
>     for j in range(0, n2):  
>         R\[j\] = arr\[m + 1 + j\]
> 
>         \# 归并临时数组到 arr\[l..r\]  
>     i = 0  \# 初始化第一个子数组的索引  
>     j = 0  \# 初始化第二个子数组的索引  
>     k = l  \# 初始归并子数组的索引
> 
>     while i < n1 and j < n2:  
>         if L\[i\] <= R\[j\]:  
>             arr\[k\] = L\[i\]  
>             i += 1  
>         else:  
>             arr\[k\] = R\[j\]  
>             j += 1  
>         k += 1
> 
>     \# 拷贝 L\[\] 的保留元素  
>     while i < n1:  
>         arr\[k\] = L\[i\]  
>         i += 1  
>         k += 1
> 
>     \# 拷贝 R\[\] 的保留元素  
>     while j < n2:  
>         arr\[k\] = R\[j\]  
>         j += 1  
>         k += 1
> 
>   
> def mergeSort(arr, l, r):  
>     if l < r:  
>         m = int((l + (r - 1)) / 2)
> 
>         mergeSort(arr, l, m)  
>         mergeSort(arr, m + 1, r)  
>         merge(arr, l, m, r)
> 
>   
> arr = \[10,233,45,77, 213, 56,\]  
> n = len(arr)  
> print("原数组")  
> for i in range(n):  
>     print("%d" % arr\[i\]),
> 
> mergeSort(arr, 0, n - 1)  
> print("\\n\\n排序后的数组")  
> for i in range(n):  
>     print("%d" % arr\[i\])  
>

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70][]

[aHR0cHM6Ly93d3cucnVub29iLmNvbS93cC1jb250ZW50L3VwbG9hZHMvMjAxOS8wMy9tZXJnZVNvcnQuZ2lm]: /images/20230528/e12dc7947a8340fcbcb2f2afef2a02d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTY2OQ_size_16_color_FFFFFF_t_70]: /images/20230528/24bc6a4b89bd4a61821cc06b1175892d.png