当前位置：首页 > news >正文

排序算法-归并排序

news 2026/6/28 14:48:28

在学习归并排序之前，个人认为需要掌握双指针的相关知识（快慢指针，左右指针之类的）。

归并排序是一种运用快慢指针与递归来实现的算法

思路

拆分过程-“归”的过程

对于数组：

5 4 3 2 1

我们先把其分为两部分：

5 4 和 3 2 1 //两个都可以，看你选择

5 4 3 和 2 1 //两个都可以，看你选择

然后再对于左右两部分再次拆分，直到分成一个元素

而这个过程，我们可以运用递归来进行数组的拆分

f(0 , 4)->f(0 , 2) + f(3 , 4)->f(0 , 1) + f(2 , 2) + f(3 , 3) + f(4, 4) //返回的是边界下标

而我们就可以利用这个过程将大数组转换成小数组，最终得到一个有序的数组

排序过程-“并”的过程

我们取递归返回的其中一个过程为例：

3 4 5 和 1 2

我们定义一个临时变量来存储部分排序好的元素，假设这个变量为temp

我们先比较 3 和 1，发现 1 比较小
于是我们把 1 放入temp

继续比较 3 和 2 ，发现 2 比较小
于是我们把 2 放入temp

这个时候右数组到头了，于是我们停止比较，并且把左数组剩下的元素全放到temp里面去

于是我们得到的temp就是

1 2 3 4 5

然后我们将temp赋值给原数组，把原数组覆盖掉

我们明显可以发现，和原来相比较，原数组更加有序了（已经有序了，我们取的是排序的最后一步）

代码实现

#include<iostream> using namespace std; const int N = 1e5; int arr[N]; int temp[N]; //辅助数组 void merge_sort(int l , int r){ //递归实现归并排序 if(l >= r) return; //只有一个元素或者没有，自然有序，不用管 int m = (l + r) / 2; //这里就是把数组拆开 merge_sort(l , m); //处理左边 merge_sort(m + 1 , r); //处理右边 int i = l , j = m + 1 , k = 0; //i和j分别代表左右数组的左边界起点 k是临时变量，作为temp数组的边界 while(i <= m && j <= r){ if(arr[i] > arr[j]){ temp[k] = arr[j]; //把小的数放进来 k++; j++; }else{ temp[k++] = arr[i++]; } } //接下来判断i和j哪个没走完，把剩下的元素放进去 while(i <= m) temp[k++] = arr[i++]; while(j <= r) temp[k++] = arr[j++]; //然后把temp覆盖arr，即把temp重新赋值给arr,arr的起始位置是l和r，temp的起始位置是0 for(i = l , k = 0 ; i <= r ; i++ , k++){ arr[i] = temp[k]; } } int main(){ int n; cin >> n; for(int i = 0 ; i < n ; i++){ cin >> arr[i]; } merge_sort(0 , n - 1); //将左边界和右边界传入 for(int i = 0 ; i < n ; i++){ cout << arr[i] << ' '; } cout << endl; return 0; }