C++實(shí)現(xiàn)歸并排序算法
更新時(shí)間：2020年03月20日 07:39:02 作者：麥迪爾
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)歸并排序算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
歸并
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
算法描述
歸并操作的工作原理如下：
1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3、比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4、重復(fù)步驟3直到某一指針超出序列尾
5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾
圖示
C++代碼
#include <iostream>
using namespace std;
//比較相鄰序列
void Merge(int arr[],int temp[],int start,int mid,int end){
int i = start,j = mid + 1,k = start;
//將較小值放入申請(qǐng)序列
while(i != mid+1 && j != end+1){
if(arr[i] > arr[j])
temp[k++] = arr[j++];
else
temp[k++] = arr[i++];
}
//將多余的數(shù)放到序列末尾
while(i != mid+1)
temp[k++] = arr[i++];
while(j != end+1)
temp[k++] = arr[j++];
//更新序列
for(i = start;i <= end;i++)
arr[i] = temp[i];
}
void MergeSort(int arr[],int temp[],int start,int end){
int mid;
if(start < end){
//避免堆棧溢出
mid = start + (end - start) / 2;
//遞歸調(diào)用
MergeSort(arr,temp,start,mid);
MergeSort(arr,temp,mid+1,end);
Merge(arr,temp,start,mid,end);
}
}
int main(){
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
cout<<a[i]<<" ";
return 0;
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本篇文章介紹了，在vs2010中產(chǎn)生的ipch文件和.sdf文件的解決方法。需要的朋友參考下2013-05-05
這篇文章主要介紹了C語(yǔ)言中的文件操作詳解，使用文件可以將數(shù)據(jù)直接存放到電腦的硬盤上，做到了數(shù)據(jù)的持久化2022-07-07
C++通過循環(huán)實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要為大家詳細(xì)介紹了C++通過循環(huán)實(shí)現(xiàn)猜數(shù)字小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-09-09
c++ 網(wǎng)絡(luò)庫(kù)asio的優(yōu)勢(shì)
這篇文章主要介紹了c++ 網(wǎng)絡(luò)庫(kù)asio的優(yōu)勢(shì)，幫助大家更好的利用c++開發(fā)服務(wù)端程序，感興趣的朋友可以了解下2020-10-10
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言職工信息管理系統(tǒng)源碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++棧的數(shù)組實(shí)現(xiàn)方式，本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-05-05
C++ 基于BFS算法的走迷宮自動(dòng)尋路的實(shí)現(xiàn)
這篇文章主要為大家介紹了C++ 基于BFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
C++實(shí)現(xiàn)LeetCode(45.跳躍游戲之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(45.跳躍游戲之二),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
本篇文章是對(duì)sizeof的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
大家好，本篇文章主要講的是C++關(guān)于指針,繼承和多態(tài)介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01