归并排序（Merge Sort）是一种高效的、基于分治法的排序算法，它的稳定性和性能使其成为常用的排序方法之一。本文将详细介绍归并排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
归并排序的基本思想
归并排序的核心思想是将数组分成两个子数组，递归地对这两个子数组进行排序，然后将它们合并成一个有序数组。这个过程分为以下几个步骤：
- 分割数组： 将待排序的数组分成两个子数组，通常是平均分割。这一步持续递归，直到每个子数组只包含一个元素。
- 递归排序： 递归地对左子数组和右子数组进行排序，直到它们都变成有序数组。
- 合并数组： 将已排序的左子数组和右子数组合并成一个有序数组。合并的过程中，逐个比较左右两个数组的元素，并将较小的元素添加到结果数组中，直到两个数组都为空。
- 返回结果： 最终得到一个完全排序好的数组。
归并排序的关键在于合并过程，也就是如何将两个有序数组合并成一个有序数组。这一过程保持了相等元素的相对顺序，因此归并排序是一种稳定的排序算法。
归并排序的示例
让我们通过一个示例来理解归并排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。
- 分割数组： 首先将数组分成两个子数组
[5, 2]和[9, 3, 4]。 - 递归排序： 分别对左子数组
[5, 2]和右子数组[9, 3, 4]递归地应用归并排序。
- 对左子数组
[5, 2]进行归并排序，得到[2, 5]。 - 对右子数组
[9, 3, 4]进行归并排序，得到[3, 4, 9]。
- 合并数组： 合并已排序的左子数组
[2, 5]和右子数组[3, 4, 9]。
- 比较左右两个数组的首元素，选择较小的元素
2，将其添加到结果数组。 - 继续比较，选择
3，将其添加到结果数组。 - 接着选择
4、5、9，按顺序添加到结果数组。
- 返回结果： 最终，得到排序后的数组
[2, 3, 4, 5, 9]。
归并排序的时间复杂度
归并排序的时间复杂度非常稳定，始终为O(n*log(n))，其中n是数组的长度。这使得它适用于大型数据集和对稳定性有要求的情况。
尽管归并排序的时间复杂度相对较高，但它的性能稳定，对于各种数据集都表现出色。此外，归并排序是一种外部排序的重要算法，用于处理大型文件和数据库。
示例代码
以下是归并排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 归并排序
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [5, 2, 9, 3, 4]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)Go 归并排序
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := arr[:mid]
right := arr[mid:]
left = mergeSort(left)
right = mergeSort(right)
return merge(left, right)
}
func merge(left, right []int) []int {
result := []int{}
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func main() {
arr := []int{5, 2, 9, 3, 4}
sorted_arr := mergeSort(arr)
fmt.Println("排序后的数组:", sorted_arr)
}Java 归并排序
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightArray[i] = arr[mid + 1 + i];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4};
mergeSort(arr, 0, arr.length - 1);
System.out.print("排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}C 语言 归并排序
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArray[n1], rightArray[n2];
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightArray[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {5, 2, 9, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}以上示例代码展示了不同编程语言中的归并排序算法实现。这些示例帮助你理解归并排序的工作原理，并提供了可供参考和使用的代码示例。归并排序是一种稳定且高效的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。
