歸并排序的遞歸實現(xiàn)與非遞歸實現(xiàn)代碼
更新時間：2013年08月23日 10:16:21 作者：
以下是對歸并排序的遞歸實現(xiàn)與非遞歸實現(xiàn)代碼進行了詳細(xì)的介紹，需要的朋友可以過來參考下
歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。值得注意的是歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
算法描述
歸并操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
第二步：設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
第三步：比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置
時間復(fù)雜度：
時間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時間性能。
空間復(fù)雜度為 O(n)
比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。
賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)
歸并排序比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法。
(以上摘抄自百度百科)
代碼實現(xiàn)
自頂向上實現(xiàn)：
//使用輔助數(shù)組實現(xiàn)歸并的過程
復(fù)制代碼 代碼如下:
void MergeSort(int *aux, int *data, int l, int m, int h)
{
int k=0, i=l, j=m+1;
for(k=l; k<=h; k++)
{
if(i>m) aux[k]=data[j++];
else if(j>h) aux[k]=data[i++];
else if(data[i]<data[j]) aux[k]=data[i++];
else aux[k]=data[j++];
}
for(k=l; k<=h; k++)
data[k]=aux[k];
}
用遞歸實現(xiàn)排序的過程(自頂向下歸并)
復(fù)制代碼 代碼如下:
void Sort(int *aux, int *data, int l, int h)
{
if(l<h)
{
int m=l+(h-l)/2;
Sort(aux, data, l, m);
Sort(aux, data, m+1, h);
MergeSort(aux,data, l, m, h);
}
}
用非遞歸實現(xiàn)排序的過程(自底向上歸并)
復(fù)制代碼 代碼如下:
void NonRerMerSort(int *aux, int *data, int l, int h)
{
int i=l, j;
for(i=l; i<=h; i=2*i)
{
for(j=l; j<=h-i; j+=2*i)
MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
}
}
相關(guān)文章
MFC創(chuàng)建模態(tài)對話框和非模態(tài)對話框的方法
這篇文章主要介紹了MFC創(chuàng)建模態(tài)對話框和非模態(tài)對話框的方法,需要的朋友可以參考下2014-07-07
#if和#endif是一組同時使用的，叫做條件編譯指令。#if與#define、#include等指令一樣是由預(yù)處理器這個強大的工具處理的，預(yù)處理器可以在編譯前處理c程序，這篇文章主要介紹了C語言中#if的使用,需要的朋友可以參考下2022-11-11
利用C++和QT實現(xiàn)Log自定義日志系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了如何利用C++和QT實現(xiàn)Log自定義日志系統(tǒng),文中的示例代碼講解詳細(xì),具有一定的借鑒價值,有需要的小伙伴可以參考下2023-12-12
采用類的機制后實現(xiàn)了數(shù)據(jù)的隱藏與封裝，類的數(shù)據(jù)成員一般定義為私有成員，成員函數(shù)一般定義為公有的，依此提供類與外界間的通信接口。但是，有時需要定義一些函數(shù)，這些函數(shù)不是類的一部分，但又需要頻繁地訪問類的數(shù)據(jù)成員，這時可以將這些函數(shù)定義為該類的友元函數(shù)2022-06-06
這篇文章主要介紹了C++中g(shù)SOAP的使用詳解,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-11-11
大量的安全漏洞是由于計算機算術(shù)運算的微妙細(xì)節(jié)引起的, 具體的C語言, 諸如符號數(shù)和無符號數(shù)之間轉(zhuǎn)換, 算術(shù)運算的越界都會導(dǎo)致不可預(yù)知的錯誤和安全漏洞, 具體的案例數(shù)不勝數(shù).2012-11-11
這篇文章主要介紹了C\C++ 獲取當(dāng)前路徑實例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C++ 中類對象類型的轉(zhuǎn)化的實例詳解的相關(guān)資料,這里提供實例幫助大家學(xué)習(xí)理解這部分內(nèi)容，需要的朋友可以參考下2017-08-08
這篇文章主要介紹了C++ template用法案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
C++中默認(rèn)無參構(gòu)造函數(shù)的工作機制淺析
構(gòu)造函數(shù)主要作用在于創(chuàng)建對象時為對象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動調(diào)用,無須手動調(diào)用；析構(gòu)函數(shù)主要作用在于對象銷毀前系統(tǒng)自動調(diào)用，執(zhí)行一些清理工作2023-02-02