归并排序(Merge Sort)是一种采用分治策略的排序算法。其基本思想是将待排序的序列分成两半,分别对这两半进行排序,然后将两个已排序的半序列合并成一个完整的有序序列。这个过程可以递归进行,直到待排序序列只有一个元素为止。
以下是归并排序的基本步骤:
-
分解:将待排序的序列分为两半(如果序列长度为奇数,可以稍许偏斜)。
-
递归:对每一半分别进行归并排序。
-
合并:将两个已排序的半序列合并成一个完整的有序序列。合并的过程是:从两个半序列的起始位置开始,依次比较它们的当前元素,将较小者放入结果序列,并将相应的指针向后移动一位。当一个半序列遍历完后,将另一个半序列剩余的元素直接追加到结果序列。
时间复杂度:
- 最好情况、最坏情况、平均情况:无论输入数组的原始顺序如何,归并排序的时间复杂度均为 O(nlogn)。这是因为每次分解都将待排序序列的长度减半,递归树的高度为logn,而合并过程中需要线性扫描两个子序列,因此总的时间复杂度为 O(nlogn)。
空间复杂度:归并排序需要额外的存储空间来合并两个子序列,空间复杂度为O(n)。这是归并排序的主要缺点,特别是在处理大型数据集时,可能会受到内存限制。
稳定性:归并排序是稳定的排序算法,即相同值的元素在排序前后相对位置不会改变。
尽管归并排序的空间复杂度相对较高,但由于其稳定的排序性质和对输入数据顺序不敏感的优秀性能,尤其在处理链表、文件等不适合进行原地排序的数据结构时,归并排序仍具有很高的实用价值。以下是归并排序的Python实现:
Python
1def merge_sort(arr):
2 if len(arr) <= 1: # 基础情况:数组长度为0或1时,已是有序
3 return arr
4
5 mid = len(arr) // 2 # 找到中间位置
6 left = arr[:mid] # 左半部分
7 right = arr[mid:] # 右半部分
8
9 # 递归对左右子序列进行归并排序
10 left_sorted = merge_sort(left)
11 right_sorted = merge_sort(right)
12
13 # 合并两个已排序的子序列
14 return merge(left_sorted, right_sorted)
15
16
17def merge(left, right):
18 merged = []
19 i = j = 0
20
21 # 依次比较两个子序列的当前元素,将较小者放入结果序列
22 while i < len(left) and j < len(right):
23 if left[i] <= right[j]:
24 merged.append(left[i])
25 i += 1
26 else:
27 merged.append(right[j])
28 j += 1
29
30 # 将剩余的元素追加到结果序列
31 merged.extend(left[i:])
32 merged.extend(right[j:])
33
34 return merged
通过递归对左右子序列进行归并排序,然后调用merge
函数合并两个已排序的子序列。merge
函数中,从两个子序列的起始位置开始,依次比较并合并元素,直至一个子序列遍历完,将另一个子序列剩余元素追加到结果序列。