看漫画学C++：归并排序
归并排序体现的是一种分治的思想：
分：递归地把当前序列平均分割成两半。
合：将上一步得到的子序列合并到一起。
归并操作
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
递归法（Top-down）
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
using namespace std;// 合并void merge(int a[], int left, int mid, int right) {// 创建两个临时数组，分别存储数组a的left～mid（左边）和mid+1~right（右边）数据int m = mid - left + 1, n = right - mid;int left_a[m];int right_a[n];for (int i = 0; i < m; i++) left_a[i] = a[left + i];for (int i = 0; i < n; i++) right_a[i] = a[mid + 1 + i];// 开始合并int i = 0, j = 0, k = left;// 左边和右边各拿一个，进行比较，小的放回数组awhile (i < m && j < n) {if (left_a[i] < right_a[j]) a[k++] = left_a[i++];else a[k++] = right_a[j++];}// 如果左边还有，把左边的放回数组awhile (i < m) a[k++] = left_a[i++];// 如果右边还有，把左边的放回数组awhile (j < n) a[k++] = right_a[j++];}void mergeSort(int a[], int left, int right) {// 只要还可以分if (left < right) {// 找到中间点int mid = (left + right) / 2;// 分成两部分mergeSort(a, left, mid);mergeSort(a, mid + 1, right);// 调用自定义函数merge进行合并merge(a, left, mid, right);}}int main() {int n;cin >> n;int a[n];for (int i = 0; i < n; i++) cin >> a[i];mergeSort(a, 0, n - 1);for (int i = 0; i < n; i++) cout << a[i] << ' ';return 0;}
看漫画也能学C++？没错！编程玩家俱乐部新推出系列课程《看漫画学C++》，带你用轻松看漫画的方式来学习C++，本课程面向零基础学员，只要坚持学习并多思考和多练习，相信你一定会成为C++的编程高手！如果喜欢本课程，就收藏一下哦，转发给你的小伙伴们，大家一起来学习！