對歸并排序進行c語言編程實現,歸并排序及C語言實現

排序系列之(1)歸并排序及C語言實現

有很多算法在結構上是遞歸的:為了解決一個給定的問題,算法需要一次或多次遞歸的調用其本身來解決相關的問題。這些算法通常采用分治策略:將原問題劃分成n個規模較小而結構與原問題相似的子問題;遞歸的解決這些子問題,然后將結果合并,就能得到原問題的解。

分治模式在遞歸時一般都有三個步驟

分解:將原問題分解成一系類子問題

解決:遞歸的解各子問題。若子問題足夠小,則直接求解。

合并:將子問題的結果合并成原問題的解。

歸并排序在算法上完全依照了上述模式,操作如下。

分解:將n個元素分解成n/2個元素的子序列

解決:用合并排序法對兩個子序列遞歸地排序

合并:將子問題的結果合并原問題的解。

以下是源代碼實現

view plaincopy to clipboardprint?

void mergeSort(int a[],int left,int right)

{

int i;

// 保證至少有兩個元素

if(left < right)

{

i = (left+right)/2;

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,left,right);

}

}

void merge(int a[],int left,int right)

{

int begin1 = left;

int mid = (left+right)/2 ;

int begin2 = mid+1;

int k=0;

int newArrayLen = right-left+1;

int *b = (int*)malloc(newArrayLen*sizeof(int));

while(begin1<=mid && begin2<=right)

{

if(a[begin1]<=a[begin2])

b[k++] = a[begin1++];

else

b[k++] = a[begin2++];

}

while(begin1<=mid)

b[k++] = a[begin1++];

while(begin2<=right)

b[k++] = a[begin2++];

copyArray(b,a,newArrayLen,left);

free(b);

}

/**

* 復制數組

* source:源數組

* dest:目標數組

* len:源數組長度

* first:目標數組起始位置

*

*/

void copyArray(int source[], int dest[],int len,int first)

{

int i;

int j=first;

for(i=0;i

{

dest[j] = source[i];

j++;

}

}

void mergeSortTest()

{

int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};

int len = sizeof(a)/sizeof(int);

showArray(a,len);

mergeSort(a,0,len-1);

showArray(a,len);

}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/287129.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/287129.shtml
英文地址,請注明出處:http://en.pswp.cn/news/287129.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Android之提示錯誤Can not perform this action after onSaveInstanceState

1 問題 主頁面3個Fragment,在第三個Fragment里面開啟了Activity之后,然后想跳到第一個Fragment代碼如下 /*** 展示Fragment*/private fun showFragment(fragment: Fragment) {if (currentFragment !== fragment) {val transaction: FragmentTransaction = supportFragmentMa…

《看聊天記錄都學不會C#?太菜了吧》(6)多晦澀的專業術語原來都會那么簡單

本系列文章將會以通俗易懂的對話方式進行教學&#xff0c;對話中將涵蓋了新手在學習中的一般問題。此系列將會持續更新&#xff0c;包括別的語言以及實戰都將使用對話的方式進行教學&#xff0c;基礎編程語言教學適用于零基礎小白&#xff0c;之后實戰課程也將會逐步更新。 若…

【Python可視化】利用Numpy繪制各種統計圖表

NumPy簡介 NumPy(Numerical Python) 是 Python 語言的一個擴展程序庫,支持大量的維度數組與矩陣運算,此外也針對數組運算提供大量的數學函數庫。 NumPy 的前身 Numeric 最早是由 Jim Hugunin 與其它協作者共同開發,2005 年,Travis Oliphant 在 Numeric 中結合了另一個同性質…

這個設計原則,你認同嗎?

前言我們都知道依賴注入的方式常見的主要有三種構造函數注入屬性注入接口注入在大名鼎鼎的Spring框架中大量使用屬性注入的方式&#xff0c;屬性注入的方式寫起來那是真的爽&#xff1b;而在Asp.NetCore中則不支持屬性注入&#xff0c;如果不使用第三方庫&#xff0c;我們就只能…

Android之提示Unable to instantiate fragment***MyLikeFragment .could not find Fragment constructor

1 問題 java.lang.RuntimeException: Unable to start activity ComponentInfo{com.appsinnova.android.keepdrop/com.appsinnova.android.keepdrop.account.favorite.activity.MyLikeActivity}: androidx.fragment.app.Fragment$InstantiationException: Unable to instantiat…

SQLServer2008-鏡像數據庫實施手冊(雙機)SQL-Server2014同樣適用

SQL Server2008R2-鏡像數據庫實施手冊(雙機)SQL Server2014同樣適用 一、配置主備機 1、 服務器基本信息 主機名稱為&#xff1a;HOST_A&#xff0c;IP地址為&#xff1a;192.168.1.155 備機名稱為&#xff1a;HOST_B&#xff0c;IP地址為&#xff1a;192.168.1.156 二、主備實…

一萬字一篇文20分鐘學會C語言和Python,十四年編程經驗老鳥傳授經驗之道

前言 昨天在直播中有粉絲問我如何快速的對編程語言入門&#xff0c;我想這個問題是有必要讓大家知道的&#xff0c;相必也有很多新手對于如何快速完成編程語言的入門學習很感興趣&#xff0c;本篇文將會使用 C 語言以及 Python 為例&#xff0c;做出對比&#xff0c;讓大家對編…

C語言基于dag的基本塊優化,基于dag的基本塊優化參考.docx

基于dag的基本塊優化參考基于DAG的基本塊優化1&#xff0e;實驗目的與任務了解基本塊的DAG表示及其應用&#xff0c;掌握局部優化的基本方法。2&#xff0e;實驗要求設計一個轉換程序&#xff0c;把由四元式序列表示的基本塊轉換為DAG&#xff0c;并在構造DAG的過程中&#xff…

【Python可視化】Windows 10系統上Pyecharts安裝教程

簡單的Python庫&#xff0c;如Numpy&#xff0c;可以直接在PyCharm中自動下載并安裝。 同添加Python環境變量一樣&#xff0c;需要先添加pip環境變量。pip位于C:\Python27\ArcGIS10.8\Scripts路徑下。 WinR→cmd&#xff1a; 安裝完成&#xff01;

使用.Net分析.Net達人挑戰賽參與情況

背景C#是我2012年在大學課程中接觸的&#xff0c;.NET Framework 我也一直使用至今。從2014年.NET 開源&#xff0c;2019年發布.NET Core 3 的時候&#xff0c;公司剛好有 Nvidia Jetson 平臺 Linux 嵌入式設備的開發任務&#xff0c;.NET 又剛是適用于 Windows, Linux, 和 mac…

Android之RecycleView實現指定范圍的拖動效果

1 問題 在RecycleView里面實現指定位置的拖動效果,(這里是實現線性布局的,不是網格布局的) @Overridepublic boolean onMove(RecyclerView recyclerView, RecyclerView.ViewHolder viewHolder, RecyclerView.ViewHolder target) {Log.i(TAG, "onMove viewHolder.getA…

十分鐘如何學會C語言?掌握規律舉一反三考試提50分!

前言 上周寫了一篇 20 分鐘學會 C 語言與Python的文章——《一萬字一篇文20分鐘學會C語言和Python&#xff0c;十四年編程經驗老鳥傳授經驗之道》&#xff0c;之后見粉絲轉了一個話題“十分鐘如何學會C語言”&#xff0c;我就在想是否能夠十分鐘呢&#xff1f;答案是可以的&am…

異常何時去捕獲

在業務邏輯層捕獲異常。 工具類中不可處理異常&#xff0c;有異常要向外拋&#xff01;&#xff01;&#xff01;轉載于:https://www.cnblogs.com/swbzmx/p/5643756.html

c語言在win8系統不兼容,Win8系統中存在不兼容軟件如何解決?

最近有剛升級Win8系統的用戶反映&#xff0c;FastStone Capture截圖軟件在Win7系統中可以兼容&#xff0c;正常打開&#xff0c;可是在Win8系統中就不能兼容了&#xff0c;這讓用戶非常煩惱。那么&#xff0c;Win8系統中存在不兼容軟件如何解決呢&#xff1f;下面&#xff0c;我…

Python 3.6出現報錯解決方案:No Python 3.6 installation was detected,無法卸載Python

卸載Python 3.6時錯誤提示&#xff0c;No Python 3.6 installation was detected。 解決辦法是&#xff0c;先右鍵→更改→Repair。 然后再卸載&#xff0c;完成&#xff01;

Android之解決ScrollView嵌套RecycleView導致滑動沖突或者顯示不全的問題

1 問題 ScrollView嵌套RecycleView導致滑動沖突或者顯示不全的問題 2 解決辦法 1&#xff09;、ScrollView替換成普通布局&#xff0c;然后RecycleView用的BaseMultiItemQuickAdapter多布局來寫&#xff0c;也就是整個頁面只有一個RecycleView&#xff0c;用來取代ScrollView…

MASA Auth - 權限設計

權限術語Subject&#xff1a;用戶&#xff0c;用戶組Action&#xff1a;對Object的操作&#xff0c;如增刪改查等Object&#xff1a;權限作用的對象&#xff0c;也可以理解為資源Effect&#xff1a;規則的作用&#xff0c;如允許&#xff0c;拒絕Condition&#xff1a;生效條件…

iOS js oc相互調用(JavaScriptCore)

http://blog.csdn.net/lwjok2007/article/details/47058795轉載于:https://www.cnblogs.com/wlsxmhz/p/5645985.html

Android怎么自定義listview布局,Android ListView自定義布局

編輯&#xff1a;找一個 “開箱即用” 的帖子的末尾例子&#xff01;因為你看到多行受到影響我猜它有些事情要做系統如何回收資源&#xff0c;也許對Button的引用是不明確的。我不確定我在哪里選擇了這種做法(Android教程或我們以前的開發人員通過這些教程學習了Android)。然而…

【必懂】C語言水仙花數題解

若是大一學子或者是真心想學習剛入門的小伙伴可以私聊我&#xff0c;若你是真心學習可以送你書籍&#xff0c;指導你學習&#xff0c;給予你目標方向的學習路線&#xff0c;無套路&#xff0c;博客為證。 前言 本專欄內容將會以輕松、簡單的方式完成習題的解答&#xff0c;用…