具体代码

#include<stdio.h>

//定位
int Patrition(int* R, int start, int end)
{
    int standard = R[start];
    
    int i = start;
    int j = end;
    
    //寻找恰当位置（下文会细讲这里）
    while(i!=j)
    {
        while(i<j&&R[j]>=standard)  j--;
        
        if(i<j&&R[j]<standard)
        {
            R[i] = R[j];
            i++;
        }
        
        while(i<j&&R[i]<=standard)  i++;
        
        if(i<j&&R[i]>standard)
        {
            R[j] = R[i];
            j--;
        }   
    }
    R[i] = standard;
    return i;   
}

//这里统一用物理位置来表示 
void QuickSort(int* R, int start, int end)
{   
    if(start<end)
    {
        int index = Patrition(R,start,end);
        QuickSort(R,start,index-1);  
        QuickSort(R,index+1,end);
    }   
}

int main()
{
    int M[6] = {9,5,3,7,8,4};   
    QuickSort(M,0,5);
    for(int i=0;i<6;i++)
    {
        printf("%d  ", M[i]);   
    }
}

过程分析

快速排序的本质，说白了就是，在一个数组中，把某个数按照大小顺序放到正确的位置，将数组分为两个小的数组。如此操作，直到每个数都在自己正确的位置。

快速排序主要由两个部分组成：
1.排序操作（QuickSort），通过递归的方式，得到有序的排列。其内部工作原理就是先将数组中的一个元素定位，分为两小个，再将两小数组排序，最后整个数组就是有序的了。（另外若数组被划分为只有一个元素的情况，则直接返回）

2.定位操作（Patrition），通过逐个对比的方式，将这个数放置到正确的位置（比如A元素在数组中是第4小，那么A元素就会被放置到4号位置去）。这样一轮操作之后，这个数的左边全是小于它的，右边全是大于它的。（但是顺序不一定对）

比如说对下面这个数组的排序：

image.png

当我们调用QuickSort函数的时候，则会依次发生Patrition（定位）和两次对划分后的小数组的QuickSort操作。

Patrition操作

结合代码和图，我一步一步分析：

第一步，选择目标（也就是你要给哪个元素找到对应位置，这里我选的是首个元素）

int standard = R[start];

image.png

第二步，准备从两侧依次对数组进行遍历，所以把指针准备好：

int i = start;
int j = end;

image.png

第三步，核心步骤，寻找正确位置：

在i和j相遇之前，逐个筛选元素，若是大于基准，则放到右边去，若是小于基准，则放到左边去。

while(i!=j)
{.....}

不过需要注意的是，放元素的位置不能使原数组的数据丢失。
一开始，第一个位置的元素5已经被作为基准了，所以第一个位置现在是空的，可以存放元素。
按要求，需要从右边开始，把比基准小的元素放过来，现在j指针指的3就符合条件，所以，移动。

image.png

现在，j的内容被写了，所以现在j指针对应的位置是可写的，于是从右边开始寻找有没有比基准大的？
很显然，7就是，所以7移过去

image.png

现在又应该从右边开始找了，于是乎，0也符合条件，写到i指针所指的7的位置去。

image.png

现在可写的位置到右边去了，所以右边继续找比基准大的：

image.png

现在又该j指针动了，6比5大，不管。4比5小，写过去！

image.png

现在i指针动起来，2可以，过！1可以，也过！

当i指到4的时候，i指针和j指针相遇了，说明这其实就是基准元素5应该在的位置，所以把5写过来。

image.png

定位完成！

我再补充一下代码里的每一步的作用：

    while(i<j&&R[j]>=standard)  j--;    //右指针，如果大于基准条件，就一直向左走
        
    if(i<j&&R[j]<standard)          //如果小了，那么就把元素写过去
    {                               //Ps.另外一边的指针的位置
        R[i] = R[j];                //永远是指的可写的
        i++;                        //所以直接R[i] = R[j]
    }
        
    while(i<j&&R[i]<=standard)  i++;//左指针，如果大于基准条件，就一直向左走
        
    if(i<j&&R[i]>standard)          //如果大了，写过去
    {
        R[j] = R[i];
        j--;
    }   
    //继续循环直到i==j  （这一堆代码都在while里）

第四步，把值放到对应的位置（对应上面最后一幅图）