歸并排序

2019-11-10 22:11:32

字體：大中小

供稿：網(wǎng)友

#include<stdio.h>//歸并排序/*要點：歸并是將兩個或多個有序記錄序列合并成一個有序數(shù)列。歸并方法有多種，一次對兩個有序記錄序列進行歸并，稱為二路歸并排序，也有三路歸并排序及多路歸并排序。本實例是二路歸并排序。基本方法是：1、將n個記錄看成是n個長度為1的有序子表2、將兩兩相鄰的有序子表進行歸并3、重復執(zhí)行步驟2，知道歸并成一個長度為n的有序子表*/void merge(int r[],int s[],int x1,int x2,int x3) //實現(xiàn)一次歸并排序{ int i,j,k; i=x1; //第一部分的開始位置 j=x2+1; //第二部分的開始位置 k=x1; while((i<=x2)&&(j<=x3)) //當i和j都在兩個要合并的部分中時 //篩選兩部分中較小的元素放到數(shù)組s中 if(r[i]<=r[j]) { s[k]=r[i]; i++; k++; } else { s[k]=r[j]; j++; k++; } while(i<=x2) //將x1~x2范圍內(nèi)未比較的數(shù)順次加到數(shù)組r中 s[k++]=r[i++]; while(j<=x3) //將x2+1~x3范圍內(nèi)未比較的數(shù)順次加到數(shù)組r中 s[k++]=r[j++];}void merge_sort(int r[],int s[],int m,int n){ int p; int t[20]; if(m==n) s[m]=r[m]; else { p=(m+n)/2; merge_sort(r,t,m,p); //遞歸調(diào)用merge_sort()函數(shù)將r[m]~r[p]歸并成有序的t[m]~t[p] merge_sort(r,t,p+1,n); //遞歸調(diào)用merge_sort()函數(shù)將r[p+1]~r[n]歸并成有序的t[p+1]~t[n] merge(t,s,m,p,n); //調(diào)用函數(shù)將前兩部分歸并到s[m]~s[n] }}void main(){ int a[11]; int i;

end MrBread 2017-02-06