C++歸并排序算法詳解
更新時(shí)間：2022年01月16日 14:57:36 作者：JJ寫代碼
大家好，本篇文章主要講的是C++歸并排序算法詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽
一.算法簡(jiǎn)介
歸并排序算法的平均時(shí)間復(fù)雜度是O(nlogn)，歸并算法的實(shí)現(xiàn)就是通過(guò)分冶法，將一個(gè)待排序列分成一個(gè)個(gè)小的序列，然后對(duì)這些小的序列進(jìn)行排序，然后進(jìn)行合并，合并的時(shí)候也會(huì)進(jìn)行排序，這樣，從整體拆成小塊，再?gòu)男K合成整體的一個(gè)過(guò)程。
二.實(shí)現(xiàn)過(guò)程
1）拆分待排序列
2）進(jìn)行排序合并
給大家寫了一個(gè)簡(jiǎn)單的過(guò)程以便大家理解。
這基本就是歸并排序的實(shí)現(xiàn)原理了，那么代碼是怎么實(shí)現(xiàn)的呢，下面給大家展示下代碼實(shí)現(xiàn)。
//時(shí)間復(fù)雜度是nlogn
#include <iostream>
using namespace std;
void Merge(int a[],int s,int mid,int e,int tmp[]);//歸并
void Merge_Sort(int a[],int s,int e,int tmp[]);//有序
int main(){
int a[1000],tmp[1000];
int n;
cin >> n;
for(int i=0;i<n;i++)cin >> a[i];
Merge_Sort(a,0,n-1,tmp);//對(duì)數(shù)組進(jìn)行排序
for(int i=0;i<n;i++)cout << a[i] << " ";
system("pause");
return 0;
}
void Merge_Sort(int a[],int s,int e,int tmp[]){
if(s<e){
int m=(s+e)/2;
Merge_Sort(a,s,m,tmp);//左邊有序
Merge_Sort(a,m+1,e,tmp);//右邊有序
Merge(a,s,m,e,tmp);//歸并
}
}
void Merge(int a[],int s,int mid,int e,int tmp[]){
int p1,p2,p=0;
p1=s,p2=mid+1;
//判斷大小，得到排列順序
while(p1<=mid&&p2<=e){
if(a[p1]<a[p2]){
tmp[p++]=a[p1++];
}
else{
tmp[p++]=a[p2++];
}
}
//剩余數(shù)據(jù)自動(dòng)放到末尾
while(p1<=mid){
tmp[p++]=a[p1++];
}
while(p2<=e){
tmp[p++]=a[p2++];
}
//將tmp中排好序的數(shù)組拷貝到a中
for(int i=0;i<e-s+1;++i){
a[s+i]=tmp[i];
}
}大家看注釋行事，注釋基本在關(guān)鍵點(diǎn)都注明了，希望對(duì)大家有幫助
總結(jié)
到此這篇關(guān)于C++歸并排序算法詳解的文章就介紹到這了,更多相關(guān)C++歸并排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言程序的編譯與預(yù)處理基礎(chǔ)定義講解
在ANSI C的任意一種實(shí)現(xiàn)中，存在2中不同的環(huán)境。第一種是翻譯環(huán)境，負(fù)責(zé)將源代碼轉(zhuǎn)換成可執(zhí)行的機(jī)器指令；第二種是執(zhí)行環(huán)境，用于實(shí)際執(zhí)行代碼。一個(gè)程序從源代碼到可執(zhí)行程序一共會(huì)經(jīng)歷四個(gè)過(guò)程，分別是預(yù)處理、編譯、匯編、鏈接，本篇讓我們來(lái)了解編譯與預(yù)處理2022-04-04
C語(yǔ)言修煉之路悟徹?cái)?shù)組真妙理?巧用下標(biāo)破萬(wàn)敵下篇
在C語(yǔ)言和C++等語(yǔ)言中，數(shù)組元素全為指針變量的數(shù)組稱為指針數(shù)組，指針數(shù)組中的元素都必須具有相同的存儲(chǔ)類型、指向相同數(shù)據(jù)類型的指針變量。指針數(shù)組比較適合用來(lái)指向若干個(gè)字符串，使字符串處理更加方便、靈活2022-02-02
這篇文章主要介紹了C++遺傳算法的一個(gè)類文件,是學(xué)習(xí)遺傳算法的絕佳參考資料,需要的朋友可以參考下2014-08-08
C++算法之在無(wú)序數(shù)組中選擇第k小個(gè)數(shù)的實(shí)現(xiàn)方法
這篇文章主要介紹了C++算法之在無(wú)序數(shù)組中選擇第k小個(gè)數(shù)的實(shí)現(xiàn)方法,涉及C++數(shù)組的遍歷、判斷、運(yùn)算等相關(guān)操作技巧,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了C++中變量的類型與作用域,C++是面向?qū)ο蟮木幊陶Z(yǔ)言,一定要注意局部變量與全局變量的作用范圍,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了?c語(yǔ)言排序之歸并排序(遞歸和非遞歸)，歸并就是把兩個(gè)或多個(gè)序列合并，本文主要介紹二路歸并，下文相關(guān)資料需要的小伙伴可以參考一下2022-04-04
這篇文章主要介紹了C++編程中對(duì)二進(jìn)制文件的讀寫操作,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
這篇文章主要介紹了sdl顯示一張bmp圖片示例,需要的朋友可以參考下2014-04-04
pair是一種模板類型，其中包含兩個(gè)數(shù)據(jù)值，兩個(gè)數(shù)據(jù)的類型可以不同,本篇詳細(xì)的介紹了Pair的使用方法和實(shí)例，有興趣的同學(xué)可以了解一下。2016-12-12
C語(yǔ)言中strcpy和strcat的使用和模擬實(shí)現(xiàn)
strcpy()?函數(shù)是?C語(yǔ)言中一個(gè)非常重要的字符串處理函數(shù),其功能是將一個(gè)字符串復(fù)制到另一個(gè)字符串中,strcat函數(shù)可以將一個(gè)字符串拼接到另一個(gè)字符串的末尾,本文給大家介紹了C語(yǔ)言中strcpy和strcat的使用和模擬實(shí)現(xiàn),需要的朋友可以參考下2024-03-03