上次在面试了一次后台开发的时候，然后在交流群里和小伙伴们交流了一下，发现数据结构和算法手撕代码是大家的弱点（包括我自己也是，对数据结构和算法也没有去系统的学习过，这方面非常差劲！），为此自己趁这段时间比较充裕一点，反正也没啥事，少刷点视频，就顺便来系统学习基本的数据结构和算法了，多掌握点技能，提高自己的思维能力，虽然在实际工作当中去写数据结构或者算法的地方几乎不会用到（当然也跟岗位有关，自身的职业岗位深入有关。。。），还是非常值得去学习，只有好处，没有坏处！

今天给大家分享的是快速排序，最为重要的是学习它的核心思想，其次再是代码实现！

一、快速排序：

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，不满足条件，就停止下来：

/ B  l7 E' r! C2 |* r

这个时候我们分析指针j,它此时指向的数字是2,不符合条件，就停止下来，同时这个时候不能进行交换数据了！

3、代码实现：

现在我们就用代码实现快排实现：

#include <iostream>
using namespace std;
1 y- {* O/ e. ^" y6 q) t5 oconst int N = 100010;
  O& A, b' l+ }" W4 n$ |int n;
int q[N];

& |& M3 C2 I5 G' a& E7 f- ovoid quick_sort(int q[], int l, int r)
9 n9 {/ ]: N0 Q4 O% H. E6 U{
2 p( }1 E$ _! x% u1 V    if(l>=r) return;//表示如果只有一个数或者0个数，就不用进行排序了
) g/ S% F4 {9 K1 T. t2 Q+ L( m- g    //确定分界点
    int x = q[l+r>>1], i = l-1, j = r+1;
    //调整区间
: `" g9 s$ T3 w+ f    while(i<j)
. S# o7 M% G: b6 h' c$ B    {
* J9 c; ]6 B* W        do i++;while(q<x);
9 `& Q- S5 Y2 Z1 c: K+ v        do j--;while(q[j]>x);
) N" p+ E# a: V  m: S5 {; ~        if(i<j)
        {
           swap(q,q[j]);
        }
    }
, T+ K: f( m. Y, k" ^8 Z# v    //进行递归
4 j) x7 Y/ O6 S% e( f( E9 v    quick_sort(q,l,j);//先对左半边递归排序
    quick_sort(q,j+1,r);//再对右半边递归排序
& p" d  }2 f9 l$ \5 t   
}
int main()
{
  w, u, N7 T2 n4 }5 O! t1 V    scanf("%d",&n);
0 c6 D+ k8 p* E: {0 G+ P) _& [1 d    for(int i =0; i<n;i++)
7 N8 X) l; ?& f" \    {
& x$ P/ G) B7 Y7 H1 ]8 O        scanf("%d",&q);
    }
    quick_sort(q, 0 , n-1);
& o2 Z# F$ B* O6 t' s, U    for(int i =0;i<n;i++)
" D6 H+ ?! L8 n" g    {
: V) I9 J/ u  B  D! a5 C4 S( o  g        printf("%d ",q);
( J, a; B1 o3 V2 U* q$ L    }
}
, [  T5 Z2 c  T+ @0 @" y8 j. ^

结果：