归并排序的代码（归并排序的代码c）

归并排序

简介

归并排序是一种稳定的、基于比较的排序算法。它的工作原理是将一个无序数组递归地分解成更小的子数组，对子数组进行排序，然后将排序后的子数组合并成一个最终已排序的数组。

算法步骤

1. 基本情况

如果数组只有一个元素，则它已经排序好，直接返回。

2. 分解

将数组分解成两个相等或近乎相等的子数组。

3. 递归

对每个子数组递归地应用归并排序。

4. 合并

将两个排序后的子数组合并成一个排序后的数组。

Python 代码

```python def merge_sort(arr):"""对给定数组进行归并排序。参数：arr：要排序的数组返回：已排序的数组"""# 检查基本情况if len(arr) <= 1:return arr# 分解数组mid = len(arr) // 2left_half = merge_sort(arr[:mid])right_half = merge_sort(arr[mid:])# 合并两个排序后的子数组return merge(left_half, right_half)def merge(left, right):"""合并两个已排序的数组。参数：left：第一个已排序数组right：第二个已排序数组返回：合并后已排序的数组"""i = 0 # left 数组的索引j = 0 # right 数组的索引merged = [] # 合并后的数组while i < len(left) and j < len(right):if left[i] <= right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1# 添加剩余元素merged.extend(left[i:])merged.extend(right[j:])return merged ```

复杂度分析

时间复杂度：

O(n log n)

空间复杂度：

O(n)

示例

```python arr = [5, 2, 8, 3, 1, 9, 4, 7, 6] sorted_arr = merge_sort(arr) print(sorted_arr) # 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9] ```