尾递归优化快速排序

 尾递归与递归效率差不多，但是可以减少递归深度。

#include<stdio.h>


/*
 * 关于使用尾递归优化快速排序算法*/


/* 划分函数*/
int
Partition(int *list,int low , int high){
    int pivot;

    pivot = *(list + low);
    while (low < high)
    {
        while (low < high && *(list + high) >= pivot)
            high--;
        *(list+low) = *(list+high);
        while (low < high && *(list + low) < pivot)
            low++;
        *(list+high) = *(list+low);
    }
    *(list+low) = pivot;
    return low;
}

/* quick sort*/
void
quicksort(int *list,int low,int high){
    int pivot;

    while (low < high){
        pivot = Partition(list,low,high);
        if (pivot - low < high - pivot)
        {
            quicksort(list,low,pivot - 1);
            low = pivot + 1;
        }
        else
        {
            quicksort(list,pivot + 1,high);
            high = pivot - 1;
        }
        //quicksort(list,pivot+1,high);
        //quicksort(list,low,pivot-1);
    }
}

int
main(int argc,char* argv[])
{
    int list[] = {5,2,45,12,32,34,4,7,23,2};
    int i;
    for (i = 0;i < 10;i++)
        printf("%d ",list[i]);
    putchar('\n');

    quicksort(list,0,9);

    for (i = 0;i < 10;i++)
        printf("%d ",list[i]);
    putchar('\n');
    return 0;
}