> 🚀write in front🚀
> 📝个人主页：认真写博客的夏目浅石.
> 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
> 📣系列专栏：[AcWing算法学习笔记](https://blog.csdn.net/congfen214/category_12113497.html?spm=1001.2014.3001.5482)
> 💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
> ✉️==如果无聊的话，就来逛逛我的博客栈吧==[stack-frame.cn](https://stack-frame.cn/)
@[TOC](文章目录)
---
# 前言
之前其实做过关于快速排序以及归并排序的博客笔记，但是我觉得我讲解的是不到位，所以我打算重新写一篇博客来帮助自己和大家梳理一下这两个算法模板以及配套的习题。
---
`其实就是把元素放到x的两侧`
# 一、快速排序
## 1.1快速排序的知识讲解
**快速排序的核心思想**：==基于分治==
**快速排序主要的内容就是：**
- 确定分界点：q[L],q[(L+R)/2],q[R] `其实就是分为左边界，中间值和右边界，甚至随机一个数`
- 调整区间，`其实就是把元素放到x的两侧`
- 递归处理左右两段
下面就是具体==讲解步骤二的调整区间==
- 两个指针，i，j不断在这里面移动
- 当指针i==指向的元素<=x的时候就指针向右移动==，==同理指针j遇到>=x的时候就==指针向左移动
- 当i指针==指向的元素>=x的时候停下来==，等到j指针==指向的元素<=x的时候就也停下来==
- 最后使得这==两个元素进行swap交换一下==
==以上就是快速排序的基础知识啦==，下面就要讲解一些习题来==巩固和练习==我们所讲解的知识点啦
**快排思想图:**
## 1.2快速排序的习题讲解
C语言实现：
```c
#include<stdio.h>
int arr[100010];
void quick_sort(int arr[],int l,int r)
{
if(l>=r) return;
int i=l-1,j=l+1,x=arr[l];
while(i<j)
{
do i++;while(arr[i]>x);
do j--;while(arr[j]<x);
if(i<j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++) printf("%d ",arr[i]);
return 0;
}
```
C++实现：
```cpp
#include <iostream>
using namespace std;
const int N = 1000010;
int q[N];
void quick_sort(int q[],int l,int r)
{
if (l>=r) return;
int i=l-1, j=r+1,x=q[l+r>>1];
while (i<j)
{
do i++; while (q[i]<x);
do j--; while (q[j]>x);
if (i<j) swap(q[i], q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j + 1,r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i=0; i<n; i++) scanf("%d", &q[i]);
quick_sort(q,0,n-1);
for (int i=0; i<n;i ++) printf("%d ", q[i]);
return 0;
}
```
```c
#include<stdio.h>
void quick_sort(int arr[],int l,int r)
{
if(l>=r) return;
int i=l-1,j=r+1,x=arr[l];
while(i<j)
{
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main()
{
int arr[100010];
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++)
{
if(i+1==k) printf("%d",arr[i]);
}
return 0;
}
```
其实C++和这个差不多，这里==不再赘述==了。
## 1.3对于快排的总结
其实就是自己要多练习几遍，反复敲打上几次就可以啦，然后隔一段时间再写一次看看自己是否可以再次写出来这个模板。
# 二、归并排序
## 2.1归并排序的知识讲解
**归并排序的核心思想**：==基于分治==
**归并排序主要的内容就是：**
- 确定分界点==mid=（left+right）/2==
- 递归排序left，right
- 归并,合二为一
下面就讲解一下，归并排序的==大致思路==：
- 先比较两个指针所指向的元素==谁大谁小==
- 谁小就拿下来放到新的保存数组里面，然后==指针向后挪动一位==，==依次类推==
- 直到其中==一个指针走向了终点的位置为止==，就可以把没有走完的直接补充到我们的==保存数组里面==
==归并排序的原理动图：==
## 2.2归并排序的习题讲解
```c
#include<stdio.h>
const int N=100010;
int arr[N],tmp[N];
void merge_sprt(int arr[],int l,int r)
{
if(l>=r) return;
int mid=(l+r)/2;
merge_sprt(arr,l,mid),merge_sprt(arr,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(arr[i]<=arr[j]) tmp[k++]=arr[i++];
else tmp[k++]=arr[j++];
}
while(i<=mid) tmp[k++]=arr[i++];
while(j<=r) tmp[k++]=arr[j++];
for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
merge_sprt(arr,0,n-1);
for(int i=0;i<n;i++) printf("%d ",arr[i]);
return 0;
}
```
---
## 2.3对于归并的总结
==主要对于逆序对问题很重要归并排序。==
# 总结
今天重新写了一篇关于AcWing算法基础课的一篇博客，其实我第一次看的时候会觉得很难，但是今天又看了一遍，发现，简单了很多，或许我们曾经不会的，或许以后就会慢慢掌握，==希望遇到困难的时候第一想到的不是退缩和放弃，而是拼尽全力试一试看看到底自己能不能行。==
我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能==一键三连==支持一下博主，hhhh~我们下期见喽
==如果无聊的话，就来逛逛我的博客栈吧==[stack-frame.cn](https://stack-frame.cn/)
>✨$\textcolor{blue}{原创不易，还希望各位大佬支持一下}$ <br/>
>👍 $\textcolor{9c81c1}{点赞，你的认可是我创作的动力！}$ <br/>
>⭐️ $\textcolor{ed7976}{收藏，你的青睐是我努力的方向！}$ <br/>
>✏️ $\textcolor{98c091}{评论，你的意见是我进步的财富！}$ <br/>
