归并排序简介【算法 11】

本文主要是介绍归并排序简介【算法 11】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序简介

归并排序（Merge Sort）是一种有效的、稳定的、基于分治法的排序算法。它的核心思想是将数组分成更小的部分，分别进行排序后再合并。归并排序具有 (O(n \log n)) 的时间复杂度，在处理大规模数据时表现优异。

---

算法原理

归并排序的工作原理基于“分治法”（Divide and Conquer），即：

1. 分解（Divide）：将未排序的数组一分为二，直到每个子数组仅包含一个元素。
2. 合并（Conquer）：将两个有序的子数组合并成一个有序数组。

具体步骤如下：

1. 将数组从中间划分为两个子数组。
2. 对两个子数组分别进行归并排序。
3. 合并两个有序的子数组。

归并过程详解

合并两个有序数组的步骤如下：

1. 创建一个临时数组 temp，用于存储合并后的数组。
2. 使用两个指针分别指向两个子数组的起始位置，比较这两个位置上的元素，将较小的元素放入 temp，指针后移。
3. 重复上述操作，直到某一个子数组遍历完成。
4. 将未遍历完的子数组剩余元素直接放入 temp。

算法实现

以下是 C 语言中归并排序的实现代码：

#include <stdio.h>// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int leftArr[n1], rightArr[n2];// 分别拷贝左右子数组for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];for (int j = 0; j < n2; j++)rightArr[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;// 合并两个有序数组while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}// 将剩余元素放入原数组while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[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);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr)/sizeof(arr[0]);printf("Given array is \n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf("\nSorted array is \n");printArray(arr, arr_size);return 0;
}

复杂度分析

• 时间复杂度：归并排序的时间复杂度为 (O(n \log n))，其中 (n) 是数组的元素个数。由于每次都将数组分成两部分，而每次合并操作的时间是线性的，因此总的时间复杂度是对数级别的。

• 空间复杂度：归并排序需要额外的空间来存储临时数组，空间复杂度为 (O(n))。

归并排序的优点与缺点

优点：

1. 稳定性：归并排序是一种稳定的排序算法，能保证相等元素的相对顺序不变。
2. 时间复杂度较低：即使在最坏情况下，归并排序的时间复杂度依然是 (O(n \log n))，表现稳定。

缺点：

1. 空间复杂度较高：由于归并排序需要额外的临时存储空间，空间消耗较大。
2. 不适合小规模数据：对于数据规模较小的数组，归并排序相比于插入排序等更高效的排序算法不具优势。

---

结论

归并排序在处理大规模数据时非常高效，适合需要稳定排序的场景。尽管其空间复杂度较高，但其时间复杂度较低且性能稳定，在很多实际应用中具有广泛的应用前景。

这篇关于归并排序简介【算法 11】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---