归并排序算法图文详解
- 作者: _微凉先森
- 来源: 51数据库
- 2022-09-23
归并排序是一种基于分治思想的排序算法，时间复杂度为O(nlogn)，效率仅次于快速排序算法。
归并排序算法的基本原理
下面我们以对序列 {7,5,2,4,1,6,3,0} 进行升序排序为例，给您讲解归并排序算法的运行流程。
整个归并排序算法的实现过程分为以下 2 步：
1) 划分（分割）
依照“分而治之”的思想，先将 {7,5,2,4,1,6,3,0} 整个序列划分为多个仅包含 1 个元素的序列，划分过程如图 1 所示：
图 1 归并排序划分序列的过程
由此，序列 {7,5,2,4,1,6,3,0} 被划分成了 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这几个元素个数仅为 1 的序列。
2) 归并（合并）
在第 1 步的基础上，接下来对 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这些序列做归并操作。
归并的核心思想是：不断地进行两两合并，合并过程中完成对新序列的排序操作。整个归并如图 2 所示。
图 2 归并所有的子序列
很明显，归并排序很适合用递归的方式实现。接下来，我们就来学习如何实现归并排序算法。
归并排序算法的具体实现
根据归并排序“先分割，后归并”的实现过程，如下伪代码描述了“分割”过程的具体实现：
输入 arr[n] // 输入要排序的序列
merge_sort(arr[n] , p , q): // [p , q] 表示对第 p ~ q 区域内的元素进行归并排序
if p < q : // 对 [p , q] 区域不断采用对半分割的方式，最终将整个区域划分为多个仅包含 1 个元素（p==q）的序列
mid = ?(x+y)/2?
merge_sort(arr , p , mid)
merge_sort(arr , mid+1 , q)
// merge(arr , p , mid , q) // 调用实现归并过程的代码模块
如下伪代码描述了“归并”过程的具体实现：
merge(arr[n] , p , mid , q): // 该算法表示将 [p , mid] 和 [mid+1 , q] 做归并操作
leftnum <- mid - p + 1 // 统计 [p , mid] 区域内的元素个数
rightnum <- q - mid // 统计 [mid+1 , q] 区域内的元素个数
leftarr[leftnum] <- arr[p ... mid] // 分别将两个区域内的元素各自拷贝到另外两个数组中
rightarr[rightnum] <- arr[mid+1 ... q]
i <- 1 , j <- 1
for k <- p to q : // 从 leftarr 和 rightarr 数组中第 1 个元素开始，每次各拿出一个元素并比较大小，将较小的元素拷贝到 arr 数组的 [p , q] 区域中
if leftarr[i] ≤ rightarr[j] :
arr[k] = leftarr[i]
i <- i+1
else :
arr[k] = right[j]
j <- j+1
归并过程是对两个区域内元素进行重组（重新排列组合）的过程，整个过程经历了以下几个步骤：
将 2 个区域（[p , mid] 和 [mid+1, q]）内的元素各自拷贝到另外两个数组（leftarr 和 rightarr）中；
从 leftarr 和 rightarr 中各自取出 1 个元素，进行大小比较；
将较小的元素拷贝到 [p , q] 区域内，并从较小元素所在的数组中取出下一个元素，再进行比较...；
循环执行第 3 步，直至 leftarr 和 rightarr 数组中的各个元素全部拷贝到 arr 数组中的 [p , q] 区域内为止。
如下是实现归并排序算法的 C 语言程序：
#include <stdio.h>
//实现分割操作的函数
void merge_sort(int* arr, int p, int q);
//实现归并操作的函数
void merge(int* arr, int p, int mid, int q);
int main() {
int i = 0;
int arr[8] = { 7,5,2,4,1,6,3,0 };
//对 arr 数组中第 1 至 8 个元素进行归并排序
merge_sort(arr, 1, 8);
while (i < 8)
{
printf("%d ", arr[i]);
i++;
}
return 0;
}
//实现分割操作的函数，[p,q] 用于指定归并排序的区域范围，
void merge_sort(int* arr, int p, int q) {
int mid;
if (arr == NULL || p > q || p == q) {
return ;
}
mid = (p + q) / 2;
//将 [p,q] 分为[p,mid] 和 [mid+1,q] 区域
merge_sort(arr, p, mid);
merge_sort(arr, mid + 1, q);
//对分好的 [p,mid] 和 [mid,q] 进行归并操作
merge(arr, p, mid, q);
}
//实现归并操作的函数，归并的 2 个区域分别为 [p,mid] 和 [mid+1,q]
void merge(int* arr, int p, int mid, int q) {
int i,j,k;
int leftarr[100], rightarr[100];
int numL = mid - p + 1;
int numR = q - mid;
//将 arr 数组中 [p,mid] 区域内的元素逐一拷贝到 leftarr 数组中
for (i = 0; i < numL; i++) {
leftarr[i] = arr[p - 1 + i];
}
//将 arr 数组中 [mid+1,q] 区域内的元素逐一拷贝到 rightarr 数组中
leftarr[i] = 2147483647;
for (i = 0; i < numR; i++) {
rightarr[i] = arr[mid + i];
}
rightarr[i] = 2147483647;
i = 0;
j = 0;
//逐一比较 leftarr 和 rightarr 中的元素，每次将较小的元素拷贝到 arr 数组中的 [p,q] 区域内
for (k = p; k <= q; k++) {
if (leftarr[i] <= rightarr[j]) {
arr[k - 1] = leftarr[i];
i++;
}
else {
arr[k - 1] = rightarr[j];
j++;
}
}
}
如下为实现归并排序算法的 Java 程序：
public class Demo {
//实现归并排序算法的分割操作
public static void merge_sort(int[] arr, int p, int q) {
// 如果数组不存在或者 [p.q] 区域不合理
if (arr == null || p >= q) {
return;
}
//对[p,q]区域进行分割
int mid = (p + q) / 2;
merge_sort(arr, p, mid);
merge_sort(arr, mid + 1, q);
//对分割的 [p,mid] 和 [mid+1,q] 区域进行归并
merge(arr, p, mid, q);
}
//实现归并排序算法的归并操作
public static void merge(int[] arr, int p, int mid, int q) {
int numL = mid - p + 1;
int numR = q - mid;
//创建 2 个数组，分别存储 [p,mid] 和 [mid+1,q]区域内的元素
int[] leftarr = new int[numL + 1];
int[] rightarr = new int[numR + 1];
int i;
for (i = 0; i < numL; i++) {
leftarr[i] = arr[p - 1 + i];
}
//将 leftarr 数组中最后一个元素设置为足够大的数。
leftarr[i] = 2147483647;
for (i = 0; i < numR; i++) {
rightarr[i] = arr[mid + i];
}
//将 rightarr 数组中最后一个元素设置为足够大的数。
rightarr[i] = 2147483647;
int j = 0;
i = 0;
//对 leftarr 和 rightarr 数组中存储的 2 个区域的元素做归并操作
for (int k = p; k <= q; k++) {
if (leftarr[i] <= rightarr[j]) {
arr[k - 1] = leftarr[i];
i++;
} else {
arr[k - 1] = rightarr[j];
j++;
}
}
}
public static void main(String[] args) {
int[] arr = new int[] { 7, 5, 2, 4, 1, 6, 3, 0 };
//对 arr 数组中第 1 至 8 个元素进行归并排序
merge_sort(arr, 1, 8);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
如下是实现归并排序算法的 Python 程序：
格式化复制
#实现归并排序算法中的分割操作，[p,q]为指定分割区域
def merge_sort(arr,p,q):
#列表中没有数据，或者 [p,q]区域不存在
if len(arr) == 1 or p >= q:
return
#对 [p,q] 区域进行分割
mid = int( (p + q) / 2 )
merge_sort(arr,p,mid)
merge_sort(arr,mid+1,q)
#归并 [p,mid] 和 [mid+1,q] 区域
merge(arr,p,mid,q)
#实现归并排序算法中的归并操作，归并区域为 [p.mid] 和 [mid+1,q]
def merge(arr,p,mid,q):
numL = mid - p + 1;
numR = q - mid;
#分别将 [p,mid] 和 [mid+1,q] 区域内的元素拷贝到 leftarr 和 rightarr 列表中
leftarr = arr[p-1:p+numL-1]
rightarr = arr[mid:mid+numR]
# 2 个列表末尾添加一个足够大的数
leftarr.append(float('inf'))
rightarr.append(float('inf'))
i=0
j=0
k=p
#逐个比较 leftarr 和 rightarr 列表中的元素，每次将较小的元素添加到 arr 列表中的 [p,q] 区域内
while k <= q:
if leftarr[i] <= rightarr[j]:
arr[k-1] = leftarr[i]
i = i + 1
else:
arr[k-1] = rightarr[j]
j = j + 1
k = k + 1
arr = [7, 5, 2, 4, 1, 6, 3, 0]
#对 arr 数组中第 1 至 8 个元素做归并排序操作
merge_sort(arr, 1, 8)
print(arr)
以上程序的输出结果均为：
0 1 2 3 4 5 6 7
