经典算法学习：排序之快速排序

快速排序

快速排序和归并排序一样，都来自分治法的思想，由于快速排序在时间复杂度为O(n*logn)的几种排序算法中效率较高，因此被经常采用。

快速排序的思想在实际的生活中经常遇到：有一堆面额不等的钞票，要把它们从小到大排序，首先可以找出一张作为基准，比它面额小的都放在左边，比它面额大的都放在右边，这时再把左右两边的进行二次处理，知道排序完成。

快速排序的步骤可以总结为如下三步：

1.找出一个基准数据

2.把比该数据小的都放在该数据左边，比该数据大的都放在该数据右边

3.重复步骤2，直到每个分组都只有一个数据

代码：

void quicksort(int s,int t,int a[])  
{  
    int i=s,j=t,x=a[(i+j)/2],y;  
    print2(a,s,t);  
    do {  
        while(a[i]<x)  
            i++;  
        while(a[j]>x)  
            j--;  
        if(i<=j)  
        {     
            y=a[j];  
            a[j]=a[i];  
            a[i]=y;  
            i++;j--;  
        }     
    }while(i<j);  
    if(j>s)  
        quicksort(s,j,a);  
    if(i<t)  
        quicksort(i,t,a);  
}