快排算法图文详解

首先粘贴C++算法代码

#include
using namespace std;
const int N=100010;
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
        do i++;while(q[i]x);
        if(i
    int n;
    cin>>n;
    for(int i=0;i>q[i];
    quick_sort(q,0,n-1);
    for(int i=0;i 
比如有这样一组数需要进行排序，为了分解问题，我们可以先选定一个数x，把比x小的数放在x的左边，把比x大的数放在x的右边，然后对已经放好的左右两边的数分别再次进行这样的操作，最后就可以达到排序的目的。思路看起来很简单，但是我们该如何实施呢?
 
有一种简单的暴力做法就是再定义两个数组A与B，将小于x的数放在A中，大于x的数放在B中，两个数组进行整合便得到了我们想要的效果，可是这样的方法似乎太占用内存，我们能不能只用这一个数组进行操作呢？答案是可以。
 
快排的思想是：如果一些数字的大小并不是按照顺序排好的，我们选定中间的数为x，并设置指针i与j分别指向首尾，首先观察i，如果i所指的数满足小于x这一条件，我们就将i加一即向右滑动指向下一个数，如果i所指的数大于x，我们就将i停下来，开始观察j所指的数是否满足大于x这一条件，若满足则一直向左滑动，若不满足则停下来，交换i与j所指的数，直到i>=j。
 
刚开始的时候i指向5，j指向14，x=8，注意这里的i与j都只是指向，而x是直接赋值，由于5<8满足条件，所以我们将i向右滑动。
 
 
13大于8，不满足q[i]x，14大于8，满足条件，所以j要向左移。
 
 由于q[j]>x一直满足，我们一直将j往左移。
 
 
 
 此时q[j]=x，不满足q[j]>=x这一条件，于是j停留在这里，不再自减，由于此时i 
 
此时第一次判断已经完毕，我们再次开始i的滑动
 
 
满足条件，我们继续将i向右滑动
 
 此时13>8，不满足条件，所以i停下，我们开始移动j。
 
 
由于4<8也不满足j的条件，所以j也停止移动，由于此时i>j，所以不交换i与j指向的数，此时也不再满足循环条件，于是第一次排序结束，我们可以看到j左边的都是小于等于x的，右边都是大于x的，在不一样的数组中x值不一定在左边，也不一定在右边，比如我们这次排序是j先遇到了x值，所以交换到了左边，如果是i先遇到可能就在右边了，所以x值在哪里不用纠结，我们最后得到的排序结果是一样的。
 
此时的数组分成了左右两边，我们分别对左右两边再次进行i与j的滑动，如下图所示：
 
 
 
 i一开始指向5，满足5<8于是i向右移动，8=8，于是i停住，j指向4不满足q[j]>8，于是j也停住，因为此时i 
 我们进行第三次排序：
 
 
 进行第四次排序：
 

 
 
 
 
 
 进行第五次排序：
 
 
 
 
最终我们得到了正确的排序，快排的思想还是蛮简单的，今日算法打卡完成！