归并排序 #
1. 归并排序算法思想 #
归并排序(Merge Sort)基本思想:
采用经典的分治策略,先递归地将当前序列平均分成两半。然后将有序序列两两合并,最终合并成一个有序序列。
2. 归并排序算法步骤 #
- 分割过程:先递归地将当前序列平均分成两半,直到子序列长度为
1
。- 找到序列中心位置
mid
,从中心位置将序列分成左右两个子序列left_arr
、right_arr
。 - 对左右两个子序列
left_arr
、right_arr
分别进行递归分割。 - 最终将数组分割为
n
个长度均为1
的有序子序列。
- 找到序列中心位置
- 归并过程:从长度为
1
的有序子序列开始,依次进行两两归并,直到合并成一个长度为n
的有序序列。- 使用数组变量
arr
存放归并后的有序数组。 - 使用两个指针
left_i
、right_i
分别指向两个有序子序列left_arr
、right_arr
的开始位置。 - 比较两个指针指向的元素,将两个有序子序列中较小元素依次存入到结果数组
arr
中,并将指针移动到下一位置。 - 重复步骤
3
,直到某一指针到达子序列末尾。 - 将另一个子序列中的剩余元素存入到结果数组
arr
中。 - 返回归并后的有序数组
arr
。
- 使用数组变量
3. 归并排序动画演示 #
- 初始序列为
[6, 2, 1, 3, 7, 5, 4, 8]
。 - 将序列分解为
[6, 2, 1, 3]
,[7, 5, 4, 8]
。 - 将序列分解为
[6, 2]
,[1, 3]
,[7, 5]
,[4, 8]
。 - 将序列分为为
[6]
,[2]
,[1]
,[3]
,[7]
,[5]
,[4]
,[8]
。 - 将序列看做是
8
个长度为1
的子序列,即[6]
,[2]
,[1]
,[3]
,[7]
,[5]
,[4]
,[8]
。 - 第
1
趟排序:将子序列中的有序子序列两两归并,归并后的子序列为:[2, 6]
,[1, 3]
,[5, 7]
,[4, 8]
。 - 第
2
趟排序:将子序列中的有序子序列两两归并,归并后的子序列为:[1, 2, 3, 6]
,[4, 5, 7, 8]
。 - 第
3
趟排序:将子序列中的有序子序列两两归并,归并后的子序列为:[1, 2, 3, 4, 5, 6, 7, 8]
。得到长度为n
的有序序列,排序结束。
4. 归并排序算法分析 #
- 时间复杂度:$O(n \times \log_2n)$。归并排序算法的时间复杂度等于归并趟数与每一趟归并的时间复杂度乘积。子算法
merge(left_arr, right_arr):
的时间复杂度是 $O(n)$,因此,归并排序算法总的时间复杂度为 $O(n \times \log_2 n)$。 - 空间复杂度:$O(n)$。归并排序方法需要用到与参加排序的序列同样大小的辅助空间。因此算法的空间复杂度为 $O(n)$。
- 排序稳定性:归并排序算法是一种 稳定排序算法。
- 因为在两个有序子序列的归并过程中,如果两个有序序列中出现相同元素,
merge(left_arr, right_arr):
算法能够使前一个序列中那个相同元素先被复制,从而确保这两个元素的相对次序不发生改变。
- 因为在两个有序子序列的归并过程中,如果两个有序序列中出现相同元素,
5. 归并排序代码实现 #
|
|