合并排序(C語(yǔ)言實(shí)現(xiàn))
其基本模式如下：
分解：把一個(gè)問(wèn)題分解成與原問(wèn)題相似的子問(wèn)題
解決：遞歸的解各個(gè)子問(wèn)題
合并：合并子問(wèn)題的結(jié)果得到了原問(wèn)題的解。
現(xiàn)在就用遞歸算法，采用上面的分治思想來(lái)解合并排序。
合并排序（非降序）
分解：把合并排序分解成與兩個(gè)子問(wè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)
解決：遞歸的解各個(gè)子問(wèn)題,每個(gè)子問(wèn)題又繼續(xù)遞歸調(diào)用自己，直到"begin<end"這一條件不滿(mǎn)足時(shí)，即"begin==end"時(shí)，此時(shí)只有一個(gè)元素，顯然是有序的，這樣再進(jìn)行下一步合并。
合并：合并的子問(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類(lèi)型是32位，表示范圍是-32768-----32768。用無(wú)窮大作為靶子可以減少對(duì)兩個(gè)小數(shù)組是否為空的判斷，有了靶子，直接判斷大數(shù)組元素個(gè)數(shù)次就排完了。
在整個(gè)過(guò)程中執(zhí)行過(guò)程示如下圖：
分解+執(zhí)行時(shí)自上向下，合并時(shí)自下向上。
代碼奉上：
#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;
}
- c語(yǔ)言冒泡排序法代碼
- C語(yǔ)言實(shí)現(xiàn)排序算法之歸并排序詳解
- c語(yǔ)言實(shí)現(xiàn)冒泡排序、希爾排序等多種算法示例
- c語(yǔ)言快速排序算法示例代碼分享
- c語(yǔ)言合并兩個(gè)已排序數(shù)組的示例(c語(yǔ)言數(shù)組排序)
- 用c語(yǔ)言實(shí)現(xiàn)冒泡排序,選擇排序,快速排序
- C語(yǔ)言排序算法之插入排序
- C語(yǔ)言實(shí)現(xiàn)選擇排序、冒泡排序和快速排序的代碼示例
- 用C語(yǔ)言實(shí)現(xiàn)從文本文件中讀取數(shù)據(jù)后進(jìn)行排序的功能
- C語(yǔ)言實(shí)現(xiàn)3個(gè)數(shù)從小到大排序/輸出的方法示例
相關(guān)文章
俄羅斯方塊是一個(gè)最初由阿列克謝帕吉特諾夫在蘇聯(lián)設(shè)計(jì)和編程的益智類(lèi)視頻游戲。本文將利用Matlab實(shí)現(xiàn)這一經(jīng)典的小游戲，需要的可以參考一下2022-03-03
這篇文章主要介紹了C語(yǔ)言寫(xiě)一個(gè)散列表,散列表，就是下標(biāo)可以為字母的數(shù)組。更多內(nèi)容和小編一起學(xué)習(xí)下面內(nèi)容吧2022-01-01
今天小編就為大家分享一篇關(guān)于C語(yǔ)言制作簡(jiǎn)易金山打字通功能的代碼，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
Qt實(shí)現(xiàn)編輯數(shù)據(jù)庫(kù)數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細(xì)介紹了Qt是如何實(shí)現(xiàn)編輯數(shù)據(jù)庫(kù)數(shù)據(jù)的，文中的示例代碼簡(jiǎn)潔易懂，對(duì)我們深入了解QT有一定的幫助，感興趣的小伙伴可以了解一下2023-02-02
對(duì)C++了解的人都應(yīng)該知道虛函數(shù)（Virtual Function）是通過(guò)一張?zhí)摵瘮?shù)表（Virtual Table）來(lái)實(shí)現(xiàn)的。簡(jiǎn)稱(chēng)為V-Table。本文就將詳細(xì)講講虛函數(shù)表的原理與使用，需要的可以參考一下2022-08-08
C++超詳細(xì)講解強(qiáng)制類(lèi)型轉(zhuǎn)換的用法
在C++語(yǔ)言中新增了四個(gè)關(guān)鍵字static_cast、const_cast、reinterpret_cast和dynamic_cast。這四個(gè)關(guān)鍵字都是用于類(lèi)型轉(zhuǎn)換的，類(lèi)型轉(zhuǎn)換（type?cast），是高級(jí)語(yǔ)言的一個(gè)基本語(yǔ)法。它被實(shí)現(xiàn)為一個(gè)特殊的運(yùn)算符，以小括號(hào)內(nèi)加上類(lèi)型名來(lái)表示，接下來(lái)讓我們一起來(lái)詳細(xì)了解2022-06-06
Eclipse對(duì)printf()不能輸出到控制臺(tái)的快速解決方法
Eclipse對(duì)printf()不能輸出到控制臺(tái)的快速解決方法。需要的朋友可以過(guò)來(lái)參考下，希望對(duì)大家有所幫助2013-10-10
C++根據(jù)傳入的函數(shù)指針來(lái)解析需要的參數(shù)(推薦)
C++可以根據(jù)傳入的函數(shù)指針，獲取自己需要的參數(shù)類(lèi)型，然后根據(jù)參數(shù)源中獲取需要的參數(shù)，具體實(shí)現(xiàn)方式大家參考下本文2018-05-05
mfc入門(mén)教程之實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)算器
這篇文章主要介紹了mfc入門(mén)教程，手把手教你如何開(kāi)發(fā)一個(gè)簡(jiǎn)單的計(jì)算器,需要的朋友可以參考下2019-04-04
??C++11系列學(xué)習(xí)之Lambda表達(dá)式
這篇文章主要介紹了??C++11系列學(xué)習(xí)之Lambda表達(dá)式，C++11終于也引入了lambda表達(dá)式，lambda最早來(lái)源于函數(shù)式編程，現(xiàn)代語(yǔ)言慢慢都引入了這個(gè)語(yǔ)法，下文關(guān)于??C++11Lambda表達(dá)式相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04