文章目录
前言
一、快速排序
1、思路
2、模板
3、模板解释
（1）排序部分（先排序）
（2）递归部分（再微分）
4、快排的随机性
二、归并排序
1、思想
2、代码实现（c++）：
3、代码分析
递归分析（先微分）：
合并分析（再积分）：
前言
本系列将从基础算法讲起，帮助大家理解一些基础的算法思想以及好用的模板，通过画图的方式帮助大家去理解与应用。
一、快速排序
1、思路
快速排序的思想就是我们选定一个数字为标准，这个标准称之为轴（pivot）。那么我们通过双指针的遍历，将小于pivot的放在pivot的左边，将大于pivot的放在pivot的右边。这样的话左侧的数据就整体上小于右侧的数据。接着我们再对左侧的数据继续执行上述的操作，直到整体有序。
我相信大家看到上述的描述后，依然是云里雾里的，那么我将从高数中的微分思想来解释一下上述过程的宏观形式。
从上述的图示中，我们再次解释快速排序，定轴的过程就是对序列切割的过程，每次定轴以后，通过排序使得左侧小于右侧，那么整体上可分为两个元素，大于轴的和小于轴的，此时宏观上是有序的。然后，我们再将左右两侧的序列再次切割再次排序，直到不可分割。这就是我们数学当中所学的微分思想。在算法中，称之为分治。
分治的过程即代码中的递归部分，可用下面的流程图理解：
以上的图片中，仅仅是为了展示递归行为的可视化表现，忽略了排序过程。（因为作者有点懒了。）
动图如下：
总结为一句话：
快排就是先保证宏观有序，再去保证微观有序。后面讲的归排恰恰相反。
2、模板
void quick_sort(int*arr,int l ,int r)
{
if(l>=r)
return;
int p=arr[(l+r)/2];
int i=l-1,j=r+1;
while(i<j)
{
do i++;while(arr[i]<p);
do j–;while(arr[j]>p);
if(i<j)
{
swap(arr[i],arr[j]);
}
}
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
模板分析：
3、模板解释
（1）排序部分（先排序）
排序部分——保证宏观有序
我们以中间为轴。（后面解释原因）
我们宏观排序的唯一目的就是保证轴左侧的数据都小于轴，轴右侧的数据都大于轴。
我们定义两个扫描指针，一个是i，一个是j。其中i指向最左边，j指向最右边。
只要i所指向的元素小于轴，那么i就从左向右移动一个单位，这样就能保证i所走过的位置所对的元素都是小于轴的，当遇到一个大于轴的数据的时候，i停止移动，保持指向这个不满足条件的数a1。
同理，只要j所指向的数据是大于轴的，那么j就从右向左移动一个单位，这样就能保证j所走过的位置都是大于轴的，当遇到一个小于轴的数据的时候，我们就停下来，让j同样保持这个不满足条件的数a2。
我们通过我们的排序目标可以知道，a1和a2互换位置后，彼此就都满足条件了。所以我们交换两个数据。
但是在交换的时候，我们需要注意一点，我们交换的数据时，i应该指向左侧，j应该指向右侧。这样交换后才能满足条件。倘若i越过了轴，j也越过了轴，可能就存在一种情况导致原本符合条件的数据发生交换，导致不符合条件。
（2）递归部分（再微分）
递归部分——保证局部有序
递归部分就如刚才的图片所示，不断地微分轴两侧的数据，保证局部有序。具体就不作过多解释了（累了）。
4、快排的随机性
一般的模板会将最左侧设定为轴。我们先以洛谷上一道题为例：
洛谷快排模板题
我们假设以最左端为轴。提交代码：出现如下结果：
我们发现有两个超时了。假设我们以中间为轴，即刚刚的模板，我们发现完美通过：
为了解释这个问题，我们回顾一下冒泡排序：
我们以 4 3 1 1 数列为例：
对这个数列进行升序排序：
第一趟冒泡 ： 3 1 1 4
第二趟冒泡 ： 1 1 3 4
我们现在讲解一下快排的思路。
我们以最左侧为轴，由于这是降序的，所以轴右侧的数据都是小于轴的， 因此我们会将轴左侧的数据通过i,j指针都移动到左侧，此时就会得到如下结果：
第一趟快排：3 1 1 4
由于轴是4，所以我们会对轴左侧（包括轴）进行第二次排序，而3左侧的2和1依旧不符合条件，只有4符合条件，所以
第二趟快排：1 1 3 4
快排和冒泡完全吻合！！
以这样一个简单的例子，（这里不作具体的量化分析，为啥呢，因为作者水平有限，推导不严谨。），可以体会到，当我们把一个有序序列倒置的时候，快排会从nlogn退化为n2。 所以上述洛谷的题目会失效。因此，我们选定中间为轴。
二、归并排序
1、思想
当一个数组中的元素是一个的时候，此时这个数组必定是有序的。所以我们先微分，微分到一个元素为一个数组的时候，我们在合并两个有序数组，即积分。这里依然使用的是分治思想。
为什么这样做呢？
如果一个规模很大的乱序数组，我们对其进行排序，那么可想而知一般情况下，我们需要排序很多次。但是我们将其规模缩小，那么其排序的次数也会相对减少，那么我们将规模不断减小到1，此时一个数字组成的数组本身就是有序的。假设我们将其分成规模为2的数组，那么也只需要排序一次就可以将这个子序列变成有序的。因此我们就可以将一个数列不断划分，直至规模为1。然后我们再将子序列不断地排序合并。最终使得整体有序。
先保证局部有序，再通过合并数组，保证整体有序。
2、代码实现（c++）：
#include
using namespace std;
const int N=1e6+10;
int arr[N];
int b[N];
void merge_sort(int*arr,int l,int r)
{
if(l>=r)
{
return;
}
int k=0;
int mid=(r+l)>>1;
merge_sort(arr,l,mid);
merge_sort(arr,mid+1,r);
int i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(arr[i]<arr[j])b[k++]=arr[i++];
else b[k++]=arr[j++];
}
while(i<=mid)b[k++]=arr[i++];
while(j<=r)b[k++]=arr[j++];
for(int i=l,k=0;i<=r;i++)
{
arr[i]=b[k++];
}
}
int main()
{
int n;
scanf(“%d”,&n);
for(int i=0;i<n;i++)
{
scanf(“%d”,arr+i);
}
merge_sort(arr,0,n-1);
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
3、代码分析
递归分析（先微分）：
这一部分先于合并函数，而这一部分也恰好是我们分治思想的体现。具体的实现逻辑如下：
合并分析（再积分）：
归并排序分成两部分，我们先来看归并部分，即将两个有序的数列，合并成一个有序的数列。
我们假设排序的规则是升序排序，那么两个有序数列的最左侧的数字都是每个数组中最小的数字，所以我们比较两个最左端的数字便能够找出两个数组中最小的数字，然后我们将这个数字放到临时数组的最左侧。
接着，我们将含有最小数字的子列中，指向最左端的指针向右偏移，那么再将这个数字和另一个子列中最左端的数字比较，接着我们就能找到第二小的数字，然后将第二小的数字放到临时数组中的左端的第二个位置，即两个子列中第二小的数字，后面重复上述操作。
直到某个子列中的数字全部放置到临时数组中，此时退出上述的操作，然后将另一个子列中的剩余数组按顺序放置到临时数组中即可。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。