1.演算法思想：
合并排序是采用分治策略實作對N個元素進行排序的演算法，是分治法的一個典型應用和完美體現，它是一種平衡，簡單的二分分治策略，計算程序分為三步：
（1）分解：將待排序元素分成大小大致相同的兩個子序列，
（2）求解子問題：用合并排序法分別對兩個子序列遞回地進行排序，
（3）合并：將排好序的有序子序列進行合并，得到符合要求的有序序列，
例如：設待排序序列A=<8,3,2,9,7,1,5,4>,采用合并排序演算法對序列A進行排序，
#include<stdio.h>
#include<math.h>
#define maxx 105
int a[maxx];
int merge[maxx];
//合并兩個有序子序列
void Merge(int merge[],int a[],int left,int right,int middle){
int i=left,j=middle+1;
int k=left;
while(i<=middle&&j<=right){
if(a[i]<=a[j]){
merge[k++]=a[i++];
}else{
merge[k++]=a[j++];
}
}
while(i<=middle)merge[k++]=a[i++];
while(j<=right)merge[k++]=a[j++];
i=0;
for(i=left;i<=right;i++)a[i]=merge[i];
}
//合并排序演算法
void Mergesort(int a[],int left,int right){
if(left<right){
int middle=(left+right)>>1;
Mergesort(a,left,middle);
Mergesort(a,middle+1,right);
Merge(merge,a,left,right,middle);
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int i;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
Mergesort(a,0,n-1);
i=0;
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
}
return 0;
}
/*
input
10
10 9 8 7 6 5 4 3 2 1
ouput
1 2 3 4 5 6 7 8 9 10
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282576.html
標籤：其他