type
status
date
slug
summary
tags
category
icon
password
😀
归并排序（Merge Sort）是一种采用分治法（Divide and Conquer）的高效排序算法，由约翰・冯・诺伊曼在 1945 年提出。它的核心思想是将数组分成两个子数组，分别对它们进行排序，然后将排好序的子数组合并成一个最终的有序数组。

📝 主旨内容

一、算法步骤

1.分解（Divide）：将数组从中间分成两个子数组，递归地对每个子数组进行排序。
2.解决（Conquer）：当子数组长度为 1 或 0 时，视为已排序。
3.合并（Merge）：将两个已排序的子数组合并成一个有序数组。

二、C 语言实现

三、举例分析

以数组 [38, 27, 43, 3, 9, 82, 10] 为例：

💡
1.分解阶段：
💡
2.合并阶段：

四、复杂度分析

💡
时间复杂度：
每次分解将数组分成两半，每次合并需要线性时间。
💡
空间复杂度：
需要额外的临时数组来合并子数组。
💡
稳定性：稳定
相等元素的相对顺序在合并过程中保持不变。

🤗 总结归纳

算法
平均时间复杂度
最坏时间复杂度
空间复杂度
稳定性
归并排序
O(n log n)
O(n log n)
O(n)
稳定
快速排序
O(n log n)
O(n²)
O(log n)
不稳定
堆排序
O(n log n)
O(n log n)
O(1)
不稳定
插入排序
O(n²)
O(n²)
O(1)
稳定
 
💡
欢迎您在底部评论区留言，一起交流~