歸并排序
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-09-10 01:18:40 閱讀次數(shù)：2437次
歸并排序的核心思想是分治原則：即將問(wèn)題分解、解決、合并。問(wèn)題分解師將n個(gè)元素分成n/2個(gè)元素的子序列；問(wèn)題解決是用合并排序法對(duì)兩個(gè)子序列進(jìn)行遞歸排序；問(wèn)題合并是利用已排好的兩個(gè)子序列合并為新的序列，得到排序結(jié)果。可以看出，對(duì)已序序列的合并是問(wèn)題關(guān)鍵。
1.合并已序序列：過(guò)程用圖來(lái)表示吧！
#define INFTY 2147483647
void Merge(int a[],int low,int mid,int high){
int n1 = mid - low+1 , n2 = high - mid;
int* L = new int [n1+1]; //多一個(gè)哨兵元素，便于簡(jiǎn)化代碼
int* R = new int [n2+1]; //多一個(gè)哨兵元素，便于簡(jiǎn)化代碼
for(int i = 0;i < n1;++i){
L[i] = a[low + i];
}
for(int j = 0;j< n2;++j){
R[j] = a[mid + j+1];
}
L[n1] = INFTY; //哨兵元素值為正無(wú)窮
R[n2] = INFTY;
for(int i = 0,j = 0,k = low;k <= high; ++k){ //用于合并數(shù)組
if(L[i] <= R[j]){
a[k] = L[i];
++i;
}
else{
a[k] = R[j];
++j;
}
}
delete L;
delete R;
}
開(kāi)始是右序列R的第一個(gè)元素1與左序列L的第一個(gè)元素比較，由于1小于2，則將R中的1放置在歸并后的數(shù)組中，接下來(lái)比較L中值為2的元素和R中值為2的元素，結(jié)果相等，將L中的2放置在歸并后的數(shù)組中，以此類推。
代碼如下：
2.
歸并排序：
代碼：
void mergeSort(int a[],int low,int high){
if(low < high){
int mid = (low + high)/2; //規(guī)定分割點(diǎn)
mergeSort(a,low,mid); //左數(shù)組是用合并排序
mergeSort(a,mid + 1,high); //右數(shù)組是用合并排序
Merge(a,low,mid,high); //合并左右數(shù)組排序結(jié)果
}
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
