42
分治法-快速排序
问题：应用快速排序方法对一个记录序列进行生序排序（运用分治法）
策略：请读者先了解快速排序的基本概念（《数据结构》或百度百科）
如下所示是一个快速排序的完整例子：（化成中间一个数，左边的比他小，右边的比他大）
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;
}
最后更新：2017-04-03 12:55:52