思想

确定主元素，利用主元素进行数组划分，小于主元素的元素在主元素左边，大于主元素的在右边，利用递归排序。这里用到了分治思想

代码一

int partition(int a[], int p, int q)
{
    int pivot = a[p];
    int i = p;
    int j = i + 1;
    int temp;
    while (j <= q)
    {
        if(pivot > a[j])
        {
            temp = a[i+1];
            a[i+1] = a[j];
            a[j] = temp;
            i++;

        }

        j++;
    }
    temp = a[i];
    a[i] = a[p];
    a[p] = temp;

    return i;

}

void Quick_sort(int a[],int p,int q)
{
    if (p < q)
        {
            int i = partition(a,p,q);
            Quick_sort(a,p,i-1);
            Quick_sort(a,i+1,q);

            }

}

int main(void)
{
    int a[] = {2,3,1,7,6,5,0};
    int p = 0;
    int q = sizeof(a) / sizeof(int) - 1;
    Quick_sort(a,p,q);
        int i;
    for(i=0;i<=q;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;

}

代码二

//平均时间复杂度 O(NlogN)

#include<stdio.h>

int partition(int *a, int L, int R)
{
    int i = L;
    int j = R;
    int x = a[L];
    while(i < j)
    {
        //从右往左找出比x小的元素
        while (i < j && a[j] > x)
            j--;
        if (i < j)
            a[i++] = a[j];
        //从左往右找出比x大的元素
        while ( i < j && a[i] < x)
            i++;
        if(i < j)
            a[j--] = a[i];
    }

    //将主元素插入
    a[i] = x;
    return i;
}

void Quick_sort(int * a,int L, int R)
{
    if (L < R)
    {
    int p = partition(a,L,R);
    Quick_sort(a ,L,p - 1);
    Quick_sort(a,p + 1,R);
    }
}

int main(void)
{
    int a[] = {4,4,4,4,4,4,4};
    int L = 0;
    int R = sizeof(a) / sizeof(int) - 1;
    Quick_sort(a,L,R);
    int i;
    for(i = 0;i <= R; i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}