其基本模式如下：
分解：把一個(gè)問(wèn)題分解成與原問(wèn)題相似的子問(wèn)題
解決：遞歸的解各個(gè)子問(wèn)題
合并：合并子問(wèn)題的結(jié)果得到了原問(wèn)題的解。
現(xiàn)在就用遞歸算法，采用上面的分治思想來(lái)解合并排序。
合并排序（非降序）
分解：把合并排序分解成與兩個(gè)子問(wèn)題
偽代碼：
if begin < end
then mid<- int((begin + end)/2)
MERGE_SORT(A, begin, mid)
MERGE_SORT(A, mid+1, end)
MERGE(A, begin, mid, end)
合并：合并的子問(wèn)題的結(jié)果有個(gè)隱含問(wèn)題，即各個(gè)子問(wèn)題已經(jīng)是排好序的了（從兩個(gè)氮元素序列開(kāi)始合并）。做法是比較兩個(gè)子序列的第一個(gè)元素小的寫(xiě)入最終結(jié)果，再往下比較，如下圖所示：
圖中：待排序數(shù)組為2 4 6 1 3 5
把2 4 6和 1 3 5 分別存到一個(gè)數(shù)組中，比較兩個(gè)數(shù)組的第一個(gè)元素大小小者存于大數(shù)組中，直到兩小數(shù)組中元素都為32767.
這里32767 味無(wú)窮大，因?yàn)?c語(yǔ)言中 int類型是32位，表示范圍是-32768-----32768。用無(wú)窮大作為靶子可以減少對(duì)兩個(gè)小數(shù)組是否為空的判斷，有了靶子，直接判斷大數(shù)組元素個(gè)數(shù)次就排完了。
在整個(gè)過(guò)程中執(zhí)行過(guò)程示如下圖：
分解+執(zhí)行時(shí)自上向下，合并時(shí)自下向上。
代碼奉上：
void MERGE(int *A, int b, int m, int e)
{
int l = m-b+1, r = e-m, i;
int L[l+1], R[r+1];
for(i=0; i< l; i++)
{
L[i] = A[b+i];
}
for (i=0; i< r; i++)
{
R[i] = A[m+i+1];
}
L[l] = 32767;
R[r] = 32767;
l = 0;
r = 0;
for(i=0; i< e-b+1; i++)
{
if(L[l] < R[r])
{
A[b+i] = L[l];
l ++;
}
else {
A[b+i] = R[r];
r ++;
}
}
}
void MERGE_SORT(int *A, int b, int e)
{
if(b < e)
{
int m = (b + e) / 2;
MERGE_SORT(A, b, m);
MERGE_SORT(A, m+1, e);
MERGE(A, b, m, e);
}
}
int main()
{
int A[500];
int lens, i;
printf("Please Enter the lenghth of array:");
scanf("%d", &lens);
printf("Please Enter the elements of the array:");
for(i=0; i< lens; i++)
scanf("%d", &A[i]);
MERGE_SORT(A, 0, lens-1);
printf("the result of the sort is:/n");
for(i=0; i< lens; i++)
{
printf("%d ", A[i]);
}
return 0;
}
新聞熱點(diǎn)
疑難解答
圖片精選
