【数据结构详解】——归并排序（动图详解）

大家好，欢迎来到IT知识分享网。

🕒 1. 归并排序

💡 算法思想：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为二路归并。

简单来说，快速排序类似于二叉树的前序遍历：首先选择一个基准值（key），然后不断划分区间，对区间内的元素进行排序，直到整个序列有序。这个过程中，一棵二叉树也随之构建完成。

相对地，归并排序则类似于二叉树的后序遍历：它会持续划分区间，直到区间内元素有序，然后利用额外空间对元素进行排序，并将它们合并回原区间，直至整个序列有序。这个过程中，划分区间相当于达到树的最底层，而归并排序则相当于从树的底层开始向上遍历。

🕘 1.1 递归实现

💡 算法思想：首先，编译器并不知道数组中是否存在有序的序列。因此，可以将数组进行划分，一分为二，二分为四…直至每个序列只剩下一个数字。毕竟，单个数字可以被视为已经排序好的。最终，将这些被划分的序列合并起来。

具体思路是：

1. 确定递归的结束条件，求出中间数mid；
2. 进行分解，根据mid来确定递归的区间大小；
3. 递归分解完左边，然后递归分解右边；
4. 左右分解完成后，进行合并；
5. 申请新数组进行合并，比较两个数组段，记得查漏补缺；
6. 合并的时候要对齐下标，每个tmp的下标要找到array中对应的下标。

void _MergeSort(int* a, int left, int right, int* tmp) { 
    // 区间中没有元素时不再合并 if (left >= right) { 
    return; } // 划分数组，每次一分为二 int mid = (left + right) / 2; _MergeSort(a, left, mid, tmp); // 划分左区间 _MergeSort(a, mid + 1, right, tmp); // 划分右区间 // 合并有序序列 int begin1 = left, end1 = mid; // 有序序列1 int begin2 = mid + 1, end2 = right; // 有序序列2 int i = left; // 辅助数组的起始位置 // 注意结束条件为一个序列为空时就停止 while (begin1 <= end1 && begin2 <= end2) { 
    if (a[begin1] < a[begin2]) { 
    tmp[i++] = a[begin1++]; // 将较小的元素放入辅助数组中 } else { 
    tmp[i++] = a[begin2++]; // 将较小的元素放入辅助数组中 } } // 两序列不可能同时为空，将剩余元素合并到辅助数组中 while (begin1 <= end1) { 
    tmp[i++] = a[begin1++]; } while (begin2 <= end2) { 
    tmp[i++] = a[begin2++]; } // 将辅助数组中排好序的部分拷贝回原数组中 memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int)); } // 归并排序递归实现 void MergeSort(int* a, int n) { 
    assert(a); // 为归并过程分配一个临时数组，用于存储中间结果 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { 
    perror("malloc fail!"); exit(-1); } // 递归调用归并排序 _MergeSort(a, 0, n - 1, tmp); // 释放临时数组 free(tmp); tmp = NULL; } 

🕘 1.2 非递归实现

💡 算法思想：非递归实现与递归实现的思想相似。区别在于，非递归是从单个元素的组开始，逐步扩大为2个元素、4个元素的组（二倍数扩大组数），即序列划分过程和递归是相反的。如此继续，直至完成所有元素的归并。

void MergeSortNonR(int* a, int n) { 
    assert(a); // 为归并过程分配一个临时数组，用于存储中间结果 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { 
    perror("malloc fail!"); exit(-1); } // 初始化每组的元素个数为1 int gap = 1; // 当gap小于数组长度时继续归并 while (gap < n) { 
    // 记录tmp数组中的元素下标 int index = 0; // 遍历数组，将每两个gap长度的子数组进行归并 for (int i = 0; i < n; i += 2 * gap) { 
    // 归并 取小的尾插 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 当原数组中元素个数不是2^n时，最后两组会出现元素不匹配的情况 // 情况1：第一组越界或第二组全部越界 if (end1 >= n || begin2 >= n) { 
    break; } // 情况2：第二组部分越界 if (end2 >= n) { 
    end2 = n - 1; // 修正一下end2，继续归并 } // 归并两个子数组到tmp数组中 while (begin1 <= end1 && begin2 <= end2) { 
    if (a[begin1] < a[begin2]) { 
    tmp[index++] = a[begin1++]; } else { 
    tmp[index++] = a[begin2++]; } } // 如果第一个子数组还有剩余元素，直接复制到tmp中 while (begin1 <= end1) { 
    tmp[index++] = a[begin1++]; } // 如果第二个子数组还有剩余元素，直接复制到tmp中 while (begin2 <= end2) { 
    tmp[index++] = a[begin2++]; } // 将辅助数组中排好序的部分拷贝回原数组中 memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int)); } // 每次循环后将每组元素的个数翻倍 gap *= 2; } // 释放临时数组的内存 free(tmp); tmp = NULL; } 

归并排序的特性总结：

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(NlogN)
3. 空间复杂度：O(N)
4. 稳定性：稳定