歸并排序

2019-11-10 23:01:06

字體：大中小

供稿：網(wǎng)友

#include<stdio.h>//歸并排序/*要點(diǎn)：歸并是將兩個(gè)或多個(gè)有序記錄序列合并成一個(gè)有序數(shù)列。歸并方法有多種，一次對(duì)兩個(gè)有序記錄序列進(jìn)行歸并，稱為二路歸并排序，也有三路歸并排序及多路歸并排序。本實(shí)例是二路歸并排序。基本方法是：1、將n個(gè)記錄看成是n個(gè)長(zhǎng)度為1的有序子表2、將兩兩相鄰的有序子表進(jìn)行歸并3、重復(fù)執(zhí)行步驟2，知道歸并成一個(gè)長(zhǎng)度為n的有序子表*/void merge(int r[],int s[],int x1,int x2,int x3) //實(shí)現(xiàn)一次歸并排序{ int i,j,k; i=x1; //第一部分的開始位置 j=x2+1; //第二部分的開始位置 k=x1; while((i<=x2)&&(j<=x3)) //當(dāng)i和j都在兩個(gè)要合并的部分中時(shí) //篩選兩部分中較小的元素放到數(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