归并排序（Merge Sort）是一种高效的、基于分治法的排序算法，它的稳定性和性能使其成为常用的排序方法之一。本文将详细介绍归并排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
归并排序的基本思想
归并排序的核心思想是将数组分成两个子数组，递归地对这两个子数组进行排序，然后将它们合并成一个有序数组。这个过程分为以下几个步骤：
1.分割数组： 将待排序的数组分成两个子数组，通常是平均分割。这一步持续递归，直到每个子数组只包含一个元素。
2.递归排序： 递归地对左子数组和右子数组进行排序，直到它们都变成有序数组。
3.合并数组： 将已排序的左子数组和右子数组合并成一个有序数组。合并的过程中，逐个比较左右两个数组的元素，并将较小的元素添加到结果数组中，直到两个数组都为空。
4.返回结果： 最终得到一个完全排序好的数组。
归并排序的关键在于合并过程，也就是如何将两个有序数组合并成一个有序数组。这一过程保持了相等元素的相对顺序，因此归并排序是一种稳定的排序算法。
归并排序的示例
让我们通过一个示例来理解归并排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。
1.分割数组： 首先将数组分成两个子数组 [5, 2] 和 [9, 3, 4]。
2.递归排序： 分别对左子数组 [5, 2] 和右子数组 [9, 3, 4] 递归地应用归并排序。
对左子数组 [5, 2] 进行归并排序，得到 [2, 5]。
对右子数组 [9, 3, 4] 进行归并排序，得到 [3, 4, 9]。
3.合并数组： 合并已排序的左子数组 [2, 5] 和右子数组 [3, 4, 9]。
比较左右两个数组的首元素，选择较小的元素 2，将其添加到结果数组。
继续比较，选择 3，将其添加到结果数组。
接着选择 4、5、9，按顺序添加到结果数组。
4.返回结果： 最终，得到排序后的数组 [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; }
以上示例代码展示了不同编程语言中的归并排序算法实现。这些示例帮助你理解归并排序的工作原理，并提供了可供参考和使用的代码示例。归并排序是一种稳定且高效的排序算法，适用于各种应用场景，特别适合对大型数据集进行排序。
