🚀write in front🚀
📝個人主頁：認真寫博客的夏目淺石.
🎁歡迎各位→點贊👍 + 收藏?? + 留言📝
📣系列專欄：AcWing算法學習筆記
💬總結：希望你看完之后，能對你有所幫助，不足請指正！共同學習交流 🖊
??如果無聊的話，就來逛逛我的博客棧吧stack-frame.cn

---

前言

之前其實做過關于快速排序以及歸并排序的博客筆記，但是我覺得我講解的是不到位，所以我打算重新寫一篇博客來幫助自己和大家梳理一下這兩個算法模板以及配套的習題。

---

其實就是把元素放到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語言實現：

#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++實現：

#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;
}

#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歸并排序的習題講解

#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

?$原創不易，還希望各位大佬支持一下$

👍 $點贊，你的認可是我創作的動力！$

?? $收藏，你的青睞是我努力的方向！$

?? $評論，你的意見是我進步的財富！$