前言
本文介绍一种排序算法——归并排序，是常用的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。
一、归并排序简介
归并排序法是将已排序好的两个或多个数列，通过合并的方式组合成一个更大的且排好序的数列。
归并排序法的实现思路有很多，本文介绍其中一种（我觉得最好理解且最方便实现的）——2路拆分法。
- 将数列拆分为N个长度为1的数列。
- 两两合并并排序，形成N/2个长度为2的数列。
- 继续两两合并并排序，形成N/4个长度为4的数列。
- 以此类推，直到形成长度为N的总数列，完成排序。
二、算法特点
1）归并排序n个数据，一般需要处理log2n次，每次处理的时间复杂度为O(n)。因此，最坏最好和平均的时间复杂度都是O(nlog2n)。
2）稳定，合并过程不改变原序列过程。
3）空间复杂度是O(n)，需要用一个同样尺寸的额外空间做辅助。
三、代码实现
代码实现逻辑：
- 递归拆分。
- 从最小长度开始合并。
- 合并完成则排序完成。
// 合并 void Merge(vector<int> &data, int left, int mid, int right) { vector<int> temp(right - left + 1, 0); int i = left; int j = mid + 1; int k = 0; // 比较填补 while (i <= mid && j <= right) { if (data[i] <= data[j]) temp[k++] = data[i++]; else temp[k++] = data[j++]; } // 剩余填补 while (i <= mid) temp[k++] = data[i++]; while (j <= right) temp[k++] = data[j++]; // 拷贝 for (int i = 0; i < k; ++i) data[i + left] = temp[i]; } // 拆分 void Split(vector<int> &data, int left, int right) { // 拆分至长度1返回 if (left >= right) return; int mid = (left + right) / 2; // 递归 Split(data, left, mid); Split(data, mid + 1, right); Merge(data, left, mid, right); } // 归并排序 void MergeSort(vector<int> &data) { int size = static_cast<int>(data.size()); int mid = size / 2; // 递归 Split(data, 0, mid); Split(data, mid + 1, size - 1); Merge(data, 0, mid, size - 1); }
四、C++示例
#include <iostream> #include <iomanip> #include <vector> #include <string> using namespace std; // 展示当前顺序 void Show(vector<int> data) { size_t size = data.size(); for (size_t i = 0; i < size; ++i) cout << setw(4) << data[i]; cout << endl; } // 合并 int Mcount = 1; void Merge(vector<int> &data, int left, int mid, int right) { vector<int> temp(right - left + 1, 0); int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (data[i] <= data[j]) temp[k++] = data[i++]; else temp[k++] = data[j++]; } while (i <= mid) temp[k++] = data[i++]; while (j <= right) temp[k++] = data[j++]; for (int i = 0; i < k; ++i) data[i + left] = temp[i]; cout << "第" << Mcount << "次排序结果：\n"; Show(data); Mcount++; } // 拆分 void Split(vector<int> &data, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; Split(data, left, mid); Split(data, mid + 1, right); Merge(data, left, mid, right); } // 归并排序 void MergeSort(vector<int> &data) { cout << "归并排序：\n原始数据：\n"; Show(data); int size = static_cast<int>(data.size()); int mid = size / 2; Split(data, 0, mid); Split(data, mid + 1, size - 1); Merge(data, 0, mid, size - 1); cout << "排序后结果：\n"; Show(data); } // 主函数 int main() { vector<int> data = { 9,11,567,0,-2,4,2,12,18,6,9 }; // 归并排序 MergeSort(data); system("pause"); return 0; }
效果图：
综上所述，归并排序法是个比较好用的排序法，优点是速度快，稳定，缺点就是占用一定空间~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
