引言

大家好，我是泡泡，一个在算法和其他领域反复横跳的博主（虽然还没去其他领域写文）

如果你是零基础的小白 那么欢迎你来订阅我的算法详解专栏 会给你不一样的学习体验！

如果你是有基础的高手 欢迎你来对自己学过的知识进行复习 和我一起探讨算法！

如果你是大牛 允许我膜拜你三分钟

对各位有帮助的话还请三连支持一下小弟，你们的关注三连是我更新的动力！

目录

引言

算法简述

快速排序

归并排序

写在最后

---

算法简述

想必各位小伙伴都听说过八大排序，如果你没有学习过算法估计也会在c语言课上听老师讲过，这八个排序算法是冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，桶排序， 堆排序。

但是我们平时用得到的多的排序只有快排和归并，所以这里展开去讲这两个排序算法。

快速排序

快速排序是对冒泡排序的一种改进， 它是不稳定的。采用的是分治策略，以减少排序过程中的比较次数，它的最好情况为O(nlogn)，最坏情况为O(n^2)，平均时间复杂度为O(nlogn)。

快速排序的基本思想是

1、先从数列中取出一个数作为分界点

这个分界点有三种方法 第一种是取左端点 第二种是取l+r/2 也就是中间点 第三种是右端点 我们平时就用中点 因为他更快一些

2、划分成两个分区 不一定相等 让左边的分区都小于等于这个点 右边的都大于等于这个点

3、递归的给左右两端排序

光看文字不直观，我们上动态图先了解一下！

然后我们就可以基于这个思想实现一下代码

首先是定义端点

int i = l - 1,j = r + 1,x = a[l+r>>1];

这是左端点和右端点，有同学要问为什么不是l和r是l-1 r+1

因为我们这两个端点每次交换完都会向中间移动一格 所以我们选择先移动再判断 为了防止边界问题 就先设置成l-1 r+1

然后就是我们的判断代码

while(i<j)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i<j)
		{
			swap(a[i],a[j]);
		}
	}

首先就是判断 左端点小于右端点 然后我们循环判断 如果当前数组左端点小于x 那么i就++ 也就是指针继续往下走 比如我们数组里的值为

3 1 2 3 5 8 7 9 6 

此时 我们的中点在5 左端点在3左边 右端点在6右边 我们先进行++ 此时左端点在3

3 1 2 3 5 8 7 9 6

然后开始判断 如果当前的值小于5 那么i继续++

一直到中点5

3 1 2 3 5 8 7 9 6

此时左端点指针停了，然后i的值为4

开始j 一直判断大于5 也是最后会到5这里 j的值也为4

注意！因为我的数组在主函数读入是从0开始 所以我传入的左端点和右端点是0和n-1（在上面这个数据也就是8）

如果 i和j两个指针没相遇 那么让他们交换一下值。

然后我们就开始递归处理左右两边

quick_sort(l,j),quick_sort(j+1,r);

一个快速排序就写好了，我们把全部代码放上来

#include<bits/stdc++.h>
using namespace std;
int a[100001];
void quick_sort(int l,int r)
{
	if(l>=r)
	{
		return;
	}
	int i = l - 1,j = r + 1,x = a[l+r>>1];
	while(i<j)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i<j)
		{
			swap(a[i],a[j]);
		}
	}
	quick_sort(l,j),quick_sort(j+1,r);
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	quick_sort(0,n-1);
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

这边建议各位记一下这个模板（不记也行 反正有库函数），然后给大家放道简单题锻炼一下这个模板哦！

快速排序模板题点这里

归并排序

如果说快速排序用的是分治的思想，那么归并排序就是分治的体现了，他会先把所有的值分开，直到不能分为止，再去进行排序，这个过程需要一个额外的数组给我们打辅助！

比如：3 1 2 3 8 7 9 6 分治之后就是 3123  8796 然后再分 31   23   87   96，这里就不能再分了，然后我们开始排序 13   23   78   69，然后开始并起来， 1233  6789最后就是排序完成 12336789 

1、确定分界点 (l+r)/2

2、递归排序左右两边

3、合二为一（难点）

然后就是我们熟悉的gif，比较直观地看一下！

我们基于上面的思想来实现代码

先去递归左右两边

int mid = l + r >> 1;
mergesort(l,mid);
mergesort(mid+1,r);

然后我们定义一个左端点 右端点和一个k（记录第二个数组放了几个值）

int k = 0,i = l,j = mid + 1;

然后就可以开始判断了，如果左边小 那么先把左边放进第二个数组，否则把右边的放入第二个数组

while(i<=mid&&j<=r)
{
	if(a[i]<=a[j])
	{
		b[k++] = a[i++];
	}
	else
	{
		b[k++] = a[j++];
	}
}

此时我们还需要判断一下，如果左右两边没有循环完毕的情况

	while(i<=mid)
	{
		b[k++] = a[i++];
	}
	while(j<=r)
	{
		b[k++] = a[j++];
	}

最后我们把数组复原一下！

	for(int i=l,j=0;i<=r;i++,j++)
	{
		a[i] = b[j];
	}

这就是我们的归并排序核心代码了，我把全部代码放上来

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[1000010];
void mergesort(int l,int r)
{
	if(l>=r)
	{
		return;
	}
	int mid = l + r >> 1;
	mergesort(l,mid);
	mergesort(mid+1,r);
	int k = 0,i = l,j = mid + 1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			b[k++] = a[i++];
		}
		else
		{
			b[k++] = a[j++];
		}
	}
	while(i<=mid)
	{
		b[k++] = a[i++];
	}
	while(j<=r)
	{
		b[k++] = a[j++];
	}
	for(int i=l,j=0;i<=r;i++,j++)
	{
		a[i] = b[j];
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	mergesort(0,n-1);
	for(int i=0;i<n;i++)
	{
		cout<<a[i];
	}
	return 0;
}

这个模板是需要大家去记得，先理解了代码的思想和原理再去记代码 不然的话记不住的 也不会用

归并排序平时都是用在了逆序对上，这里出一个逆序对的简单题，大家可以思考一下！

逆序对简单题点这里

写在最后

学习算法是为了让自己变得更好，更优秀，路上的这些比赛都是检验你的学习成果的，如果成绩不理想也不要灰心，毕竟你不是为了比赛去学习的，学习算法需要持之以恒的练习，我希望各位都能在算法这条路上坚持下去

如果你觉得这篇文章对你有帮助或者觉得写得不错的可以订阅我的算法详解专栏并且给我一个三连关注支持一下我，你们的支持是我更新的动力，感谢各位的观看，祝你们天天开心！