算法可视化——归并排序

1.前言

时隔几个月,终于重新拾起了C++!

老司机回归,自然是“ 启动VS → 新建解决方案 → 添加新项目 ”一键三连。

啊,这丝滑的感觉,莫不是?


在这里插入图片描述


不能打断了这丝滑的感觉,随便写点什么,写个归并排序吧!

一顿操作猛如虎,一看编译。。。


在这里插入图片描述


祝大家虎虎生威!

此时的我 ⬇


在这里插入图片描述


怀念起了用Matlab做数字信号处理的日子。

自信心备受打击,卑微的我找到了某度(面向搜索引擎编程不只是说着玩儿的)。

问题答案非常简单,那就是VS的C++编译器不允许使用变量作为数组的长度定义数组。

然而gcc编译器就可以,看到这里我想卸了Visual Studio。

说到底还是基础不牢,地动山摇!

还是说说最后咋解决的吧,卸了Visual Studio是不可能的,这辈子都不可能的!

用vector代替数组就ok了,是不是so easy!


在这里插入图片描述

在这里插入图片描述

2.归并排序

归并排序基于分而治之的思想,即分解原问题、解决子问题、合并问题解
我觉得两张动图就可以完美解释归并算法的原理。

分解原问题:


在这里插入图片描述

解决子问题:
当问题分解到只有一个数的时候,自然变得有序,子问题自然解决。

合并问题解:


在这里插入图片描述

归并排序可视化:


在这里插入图片描述

2.1 归并排序的C++实现

void merge(int a[], int low, int mid, int high) {
    int N = high - low + 1;
    std::vector<int> b(N); 
    int left = low, right = mid + 1, bIdx = 0;
    while (left <= mid && right <= high) 
        b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
    while (left <= mid) b[bIdx++] = a[left++]; 
    while (right <= high) b[bIdx++] = a[right++]; 
    for (int k = 0; k < N; k++) a[low + k] = b[k]; 
}
void mergeSort(int a[], int low, int high) {
  // 要排序的数组是 a[low..high]
  if (low < high) { 
    int mid = (low+high) / 2;    
    mergeSort(a, low  , mid ); // 分成一半
    mergeSort(a, mid+1, high); // 递归地将它们排序
    merge(a, low, mid, high); // 解决: 归并子程序
  }
}

你可能也喜欢

0 0 vote
Article Rating
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
Scroll to Top