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