分治法-快速排序

问题：应用快速排序方法对一个记录序列进行生序排序（运用分治法）

策略：请读者先了解快速排序的基本概念（《数据结构》或百度百科）

如下所示是一个快速排序的完整例子：（化成中间一个数，左边的比他小，右边的比他大）

23 13 35 6 19 50 28
[19 13 6] 23 [35 50 28]
[6 13] 19 23 [28] 35 [50]
6 [13] 19 23 28 35 50
6 13 19 23 28 35 50

实现代码:

#include<stdio.h>
int r[1010]; 
int Partition(int r[],int first,int end)//划分 
{
    int i=first,j=end;//初始化待划分区间 
    while(i<j)
    {
        while(i<j&&r[i]<=r[j]) j--;//右侧扫描 
        if(i<j)
        {
               int temp=r[i];r[i]=r[j];r[j]=temp;//将较小记录交换到前面 
               i++;
        }
        while(i<j&&r[i]<=r[j]) i++;//左侧扫描 
        if(i<j)
        {
               int temp=r[i];r[i]=r[j];r[j]=temp;//将较大记录交换到后面 
               j--;
        }
    }
    return i;
}
void QuickSort(int r[],int first,int end)//快速排序 
{
     int pivot;
     if(first<end)
     {
        pivot=Partition(r,first,end);//划分，pivot是轴值在序列中的位置 
        QuickSort(r,first,pivot-1);//求解子问题1，对左侧子序列进行快速排序 
        QuickSort(r,pivot+1,end);//求解子问题2，对右侧子序列进行快速排序 
     }
} 
int main()
{
    int i,j,n,m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&r[i]);
    QuickSort(r,0,n-1);
    for(i=0;i<n;i++)
    printf("%d ",r[i]);
    puts("");
    return 0;
}