194
分治法-歸並排序
問題：應用歸並法對一個記錄序列進行升序排序（利用分治法）
思路：1.劃分
2.求解子問題
3.合並
歸並排序的執行過程：（*是拆分，#是合並）
8 3 2 6 7 1 5 4
*8 3 2 6* *7 1 5 4*
*8 3* *2 6* *7 1* *5 4*
*8* *3* *2* *6* *7* *1* *5* *4*
#3 8# #2 6# #1 7# #4 5#
#2 3 6 8# #1 4 5 7#
1 2 3 4 5 6 7 8
如果還不理解什麼是“歸並排序”，請查看百度百科或者《數據結構》
這裏不再多說，主要實現分治的解決方法
實現代碼：（數據上限：n<=1000）
#include<stdio.h>
int r[1010];
void Merge(int r[],int r1[],int s, int m,int t)//合並子序列
{
int i=s,j=m+1,k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j]) r1[k++]=r[i++];//取r[i]h和r[j]中較小者放入r1[k]
else r1[k++]=r[j++];
}
while(i<=m)//若第一個子序列沒有處理完，則進行收尾處理
r1[k++]=r[i++];
while(j<=t)//若第二個子序列沒有處理完，則進行收尾處理
r1[k++]=r[j++];
}
void MergeSort(int r[],int s,int t)//對序列r[s]~r[t]進行歸並排序
{
int i,m,r1[1010];
if(s==t) return;
else
{
m=(s+t)/2;
MergeSort(r,s,m);//求解子問題1，歸並排序前半個子序列
MergeSort(r,m+1,t);//求解子問題2，歸並排序前半個子序列
Merge(r,r1,s,m,t);//合並兩個有序子序列，結果保存在數組r1中
for(i=s;i<=t;i++)//將有序序列傳回r中
r[i]=r1[i];
}
}
int main()
{
int i,j,n,m;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&r[i]);
MergeSort(r,0,n-1);
for(i=0;i<n;i++)
printf("%d ",r[i]);
puts("");
return 0;
}
最後更新：2017-04-03 12:55:52