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