合并排序(C語言實現(xiàn))
其基本模式如下：
分解：把一個問題分解成與原問題相似的子問題
解決：遞歸的解各個子問題
合并：合并子問題的結(jié)果得到了原問題的解。
現(xiàn)在就用遞歸算法，采用上面的分治思想來解合并排序。
合并排序（非降序）
分解：把合并排序分解成與兩個子問題
偽代碼：
MERGE_SORT(A, begin, end)
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)
解決：遞歸的解各個子問題,每個子問題又繼續(xù)遞歸調(diào)用自己，直到"begin<end"這一條件不滿足時，即"begin==end"時，此時只有一個元素，顯然是有序的，這樣再進行下一步合并。
合并：合并的子問題的結(jié)果有個隱含問題，即各個子問題已經(jīng)是排好序的了（從兩個氮元素序列開始合并）。做法是比較兩個子序列的第一個元素小的寫入最終結(jié)果，再往下比較，如下圖所示：
圖中：待排序數(shù)組為2 4 6 1 3 5
把2 4 6和 1 3 5 分別存到一個數(shù)組中，比較兩個數(shù)組的第一個元素大小小者存于大數(shù)組中，直到兩小數(shù)組中元素都為32767.
這里32767 味無窮大，因為 c語言中 int類型是32位，表示范圍是-32768-----32768。用無窮大作為靶子可以減少對兩個小數(shù)組是否為空的判斷，有了靶子，直接判斷大數(shù)組元素個數(shù)次就排完了。
在整個過程中執(zhí)行過程示如下圖：
分解+執(zhí)行時自上向下，合并時自下向上。
代碼奉上：
#include <stdio.h>
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;
}
相關(guān)文章
遞歸（recursive）函數(shù)是“自己調(diào)用自己”的函數(shù)，無論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個函數(shù)（然后可能又調(diào)用第三個函數(shù)等），最后又調(diào)用第一個函數(shù)。因為函數(shù)不可以一直不停地調(diào)用自己，所以遞歸函數(shù)一定具備結(jié)束條件2022-07-07
以下是對C#中委托的基本用法進行了詳細的總結(jié)分析，需要的朋友可以過來參考下。希望對大家有所幫助2013-09-09
這篇文章主要介紹是我是C語言中的文件讀寫fseek 函數(shù)的相關(guān)資料，fseek 函數(shù)用來移動文件流的讀寫位置；就好比播放器，可以直接拖拽到精彩的時間點一樣，下面我們就來詳細介紹該內(nèi)容吧，感興趣的小伙伴可以參考一下2021-10-10
64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法
這篇文章主要介紹了64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C++中如何調(diào)用C語言的代碼實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
下面小編就為大家?guī)硪黄獪\談c語言中類型隱性轉(zhuǎn)換的坑。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-08-08
一道超經(jīng)典的C++結(jié)構(gòu)體的題目
以下小編就為大家介紹一道超經(jīng)典的關(guān)于C++結(jié)構(gòu)體的題目。需要的朋友可以過來參考下2013-09-09
大家好，本篇文章主要講的是C++實現(xiàn)和電腦對戰(zhàn)三子棋實例，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了C語言按關(guān)鍵字搜索文件夾中文件的方法,涉及C語言文件操作及字符串查找的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
C++11新特性之隨機數(shù)庫(Random?Number?Library)詳解
相對于C++11之前的隨機數(shù)生成器來說,C++11的隨機數(shù)生成器是復雜了很多,下面這篇文章主要給大家介紹了關(guān)于C++11新特性之隨機數(shù)庫(Random?Number?Library)的相關(guān)資料,需要的朋友可以參考下2022-06-06