快速排序递归解析

#include <stdio.h>
#include <stdlib.h>
int a[101],n; 
void quicksort(int left,int right){
    int i,j,temp,t;
    if(left>=right) return;
    i=left;
    j=right;
    temp=a[left];
    while(i!=j){
        while(a[j]>=temp&&i<j) j--;
        while(a[i]<=temp&&i<j) i++;
        if(i<j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];
    a[i]=temp;
    quicksort(left,i-1);
    quicksort(i+1,right);
    return;
}
int main(){
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    getchar();
    quicksort(0,n-1);
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    getchar();
    return 0;
}

第一次进入函数quicksort，首先是把3作为基准数，然后将数组中所有比3小的移到左边，具体代码流程：右边开始，找到比基准数小的数停止，再从左边开始找到比基准数大的停止，然后交换，直到左边右边相遇时循环结束，结束后把基准数和此时a[i]交换；结果如下：

箭头是指向两个标红的数字

交换完后继续移动：

现在相遇了。就退出循环,交换基准数，此时i=2：

接下来进行递归(left=0,i=2)：

quicksort(0,1);

quicksort(0,0);

此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=0，right=6);

quicksort(1,6)

这时执行这个递归时会遇到第一个递归quicksort(left,i-1);(此时left=1，i=1)

quicksort(1,1)

此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=1，right=6);

quicksort(2,6)

这时执行这个递归时会遇到第一个递归quicksort(left,i-1);(此时left=2，i=2)

quicksort(2,2)

此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=2，right=6);

quicksort(3,6)

这时执行这个递归时会遇到第一个递归quicksort(left,i-1);(此时left=3，i=5)

quicksort(3,4)

quicksort(3,3)

此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=3，right=6);

quicksort(3,6)

这时执行这个递归时会遇到第一个递归quicksort(left,i-1);(此时left=4，i=4)

quicksort(4,4) 此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=4，right=6);

quicksort(5,6)

quicksort(5,5)

此时遇到出口，进入第二个递归quicksort(i+1,right);(此时i=5，right=6);

即为quicksort(6,6)此时第二个递归结束，由于递归一直保留着之前的调用点，此时一层一层返回释放掉调用点！然后整个函数调用结束！

总结：第二个递归的作用就是控制第一个递归，能够从左到右每一个数都当作基准点执行一次排序！

快速排序递归解析

原文：https://www.cnblogs.com/sushang/p/14915622.html