合并排序(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)文章
俄羅斯方塊是一個最初由阿列克謝帕吉特諾夫在蘇聯(lián)設(shè)計和編程的益智類視頻游戲。本文將利用Matlab實現(xiàn)這一經(jīng)典的小游戲，需要的可以參考一下2022-03-03
這篇文章主要介紹了C語言寫一個散列表,散列表，就是下標(biāo)可以為字母的數(shù)組。更多內(nèi)容和小編一起學(xué)習(xí)下面內(nèi)容吧2022-01-01
今天小編就為大家分享一篇關(guān)于C語言制作簡易金山打字通功能的代碼，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
Qt實現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細(xì)介紹了Qt是如何實現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的，文中的示例代碼簡潔易懂，對我們深入了解QT有一定的幫助，感興趣的小伙伴可以了解一下2023-02-02
對C++了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過一張?zhí)摵瘮?shù)表（Virtual Table）來實現(xiàn)的。簡稱為V-Table。本文就將詳細(xì)講講虛函數(shù)表的原理與使用，需要的可以參考一下2022-08-08
在C++語言中新增了四個關(guān)鍵字static_cast、const_cast、reinterpret_cast和dynamic_cast。這四個關(guān)鍵字都是用于類型轉(zhuǎn)換的，類型轉(zhuǎn)換（type?cast），是高級語言的一個基本語法。它被實現(xiàn)為一個特殊的運算符，以小括號內(nèi)加上類型名來表示，接下來讓我們一起來詳細(xì)了解2022-06-06
Eclipse對printf()不能輸出到控制臺的快速解決方法
Eclipse對printf()不能輸出到控制臺的快速解決方法。需要的朋友可以過來參考下，希望對大家有所幫助2013-10-10
C++根據(jù)傳入的函數(shù)指針來解析需要的參數(shù)(推薦)
C++可以根據(jù)傳入的函數(shù)指針，獲取自己需要的參數(shù)類型，然后根據(jù)參數(shù)源中獲取需要的參數(shù)，具體實現(xiàn)方式大家參考下本文2018-05-05
這篇文章主要介紹了mfc入門教程，手把手教你如何開發(fā)一個簡單的計算器,需要的朋友可以參考下2019-04-04
??C++11系列學(xué)習(xí)之Lambda表達式
這篇文章主要介紹了??C++11系列學(xué)習(xí)之Lambda表達式，C++11終于也引入了lambda表達式，lambda最早來源于函數(shù)式編程，現(xiàn)代語言慢慢都引入了這個語法，下文關(guān)于??C++11Lambda表達式相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04