归并排序（Python）

悠悠 2023-01-03 04:19 128阅读 0赞

# 归并排序 #

<table> 
 <thead> 
 <tr> 
 <th>排序算法</th> 
 <th>平均时间复杂度</th> 
 <th>空间复杂度</th> 
 <th>稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305019" rel="nofollow">冒泡排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305118" rel="nofollow">选择排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86178111" rel="nofollow">插入排序</a></td> 
 <td> O ( n 2 ) O(n^2) O(n2)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86178111" rel="nofollow">希尔排序</a></td> 
 <td> O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/112305240" rel="nofollow">归并排序</a></td> 
 <td> O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n)</td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86591978" rel="nofollow">快速排序</a></td> 
 <td> O ( n log ⁡ n ) O(n\log n) O(nlogn)</td> 
 <td> O ( log ⁡ n ) O(\log n) O(logn)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86582643" rel="nofollow">堆排序</a></td> 
 <td> O ( n log ⁡ n ) O(n\log n) O(nlogn)</td> 
 <td> O ( 1 ) O(1) O(1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">计数排序</a></td> 
 <td> O ( n + k ) O(n+k) O(n+k)</td> 
 <td> O ( k ) O(k) O(k)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">基数排序</a></td> 
 <td> O ( n × k ) O(n\times k) O(n×k)</td> 
 <td></td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td><a href="https://blog.csdn.net/weixin_41308573/article/details/86632295" rel="nofollow">桶排序</a></td> 
 <td> O ( n ) O(n) O(n)</td> 
 <td> O ( m ) O(m) O(m)</td> 
 <td>稳定</td> 
 </tr> 
 </tbody> 
</table>

## 算法思路 ##

归并排序遵循分治的思想，将待排序数列分为两个有序子数列，然后合并两个有序子数列为一个完整有序数列，每个子数列也是通过相同的方式变得有序。

## 算法实现 ##

合并过程：

1.  设置指针 index 指向待排序数列的起始位置，设置两个指针 index\_l、index\_r 分别指向两个子数列的起始位置。
2.  比较 index\_l、index\_r 所指向的元素，将较小的元素写入 index 指针所指的位置，并将 index 指针以及指向较小数列元素的指针后移。
3.  重复步骤 2 知道某一子数列指针到达序列末尾。
4.  将另一数列剩余元素合并到完整数列末尾。

合并函数：

def merge(arr, start, mid, end):
 left, right = arr[start:mid+1], arr[mid+1:end+1]
 index, index_l, index_r, len_l, len_r = start, 0, 0, len(left), len(right)
 
 while index_l < len_l and index_r < len_r:
 if left[index_l] > right[index_r]:
 arr[index] = right[index_r]
 index_r += 1
 else:
 arr[index] = left[index_l]
 index_l += 1
 index += 1
 
 if index_l < len_l:
 arr[index:end+1] = left[index_l:]
 if index_r < len_r:
 arr[index:end+1] = right[index_r:]

### 递归版本 ###

def merge_sort_recursion(arr, start, end):
        if start >= end:
            return
        
        mid = (start + end) // 2
        merge_sort_recursion(arr, start, mid)
        merge_sort_recursion(arr, mid+1, end)
        merge(arr, start, mid, end)

### 迭代版本 ###

def merge_sort_iter(arr):
 arr_len = len(arr)
 if arr_len < 2:
 return
 
 seq = 1
 while seq < arr_len:
 i = 0
 while i < arr_len - seq:
 merge(arr, i, i + seq - 1, min(i + 2 * seq - 1, arr_len - 1))
 i += 2 * seq
 seq += seq

--------------------

本博客文章仅供博主学习交流，博主才疏学浅，语言表达能力有限，对知识的理解、编写代码能力都有很多不足，希望各路大神多多包涵，多加指点。