通俗易懂的快排！
上次在面試了一次後台開發的時候，然後在交流群里和小夥伴們交流了一下，發現數據結構和演算法手撕程式碼是大家的弱點（包括我自己也是，對數據結構和演算法也沒有去系統的學習過，這方面非常差勁！），為此自己趁這段時間比較充裕一點，反正也沒啥事，少刷點影片，就順便來系統學習基本的數據結構和演算法了，多掌握點技能，提高自己的思維能力，雖然在實際工作當中去寫數據結構或者演算法的地方几乎不會用到（當然也跟崗位有關，自身的職業崗位深入有關。。。），還是非常值得去學習，只有好處，沒有壞處！
今天給大家分享的是快速排序，最為重要的是學習它的核心思想，其次再是程式碼實現！
一、快速排序：
1、核心思想：
(1)、確定分界點，可以在上圖中的數軸上隨便找一個點來作為分界點，當然我們常規的確定分界點方法有：
a、直接取左邊界，表示為q[l]
b、取中間值，表示為q[(l+r)/2]
c、取右邊界，表示為q[r]
d、這種方法就是隨便取了；不過上面三種方法是我們常用的方法！
(2)、調整區間：
如上圖所以，我們把小於等於x的數字放在小於等於x的區間裡面去；把大於等於x的數字放在大於等於x的區間裡面去
(3)、遞歸處理左右兩端區間
2、具體實現細節分分析：
這裡我們用兩個指針分別為指針i、指針j,指向數軸上的兩端，如下圖所示：
讓兩個指針都往中間走，這裡我們先分析指針i，當指針i指到了小於x的數字，就把它分好位置，繼續往下走，直到遇到不符合這個條件，指針i就停止往下訪問了；接著我們來分析指針j了，方法一樣，當指針j指向的數字大於x的時候，把它分好位置，繼續往下走，直到遇到不符合這個條件，指針j就停止往下訪問了，這時進行兩邊數據互換swap();接著繼續按照這種方式往下訪問，直到排序完成為止！
這樣說可能還沒聽明白，那麼我們下面用實際的數字來說話，比如：3、1、2、3、5
這裡我們取分界點為3；我們可以看到指針i先指向3，它剛好等於3（不滿足小於3的條件，這裡的分界點3不要放入到任何的區間去，不然為啥會叫分界點），所以指針i就先暫停；然後是指針j，我們從圖中發現它指向的數字大於3,滿足條件，所以先把5放置好位置來，然後繼續讓指針j往下走：
這個時候你會發現指針j指向的數字是3，不滿足條件，所以進行i和j指向的數字進行交換swap(),這裡都是3,所以看不出啥變化來。
交換完後，繼續按照原來的方式往下走，指針i和指針j指向的數字如下：
這個時候我們會發現指針i指向的數字是1，所以符合條件，放置好位置來，繼續往下走，你會發現指向數字2，滿足條件，同樣放置好位置來，然後繼續往下走，此時指針i指向的數字是3，不滿足條件，就停止下來：
這個我們分析指針j,它此時指向的數字是2,不符合條件，就停止下來，這個時候不能進行交換數據了！
3、程式碼實現：
現在我們就用程式碼實現快排實現：
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
if(l>=r) return;//表示如果只有一個數或者0個數，就不用進行排序了
//確定分界點
int x = q[l+r>>1], i = l-1, j = 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()
{
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]);
}
}
結果：
參考：//www.acwing.com/activity/content/punch_the_clock/11/，網站:AcWing
我是txp，一個只專註於乾貨分享的部落客，歡迎隨時來撩我，我們下期見！更多精彩內容，可以微信搜索：txp玩linux；qq群：836108981
