C++實(shí)現(xiàn)歸并排序算法
歸并
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
算法描述
歸并操作的工作原理如下：
1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
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)文章
C++實(shí)現(xiàn)分?jǐn)?shù)計(jì)算器
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)分?jǐn)?shù)計(jì)算器，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了c++ String去除頭尾空格的方法,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
適合初學(xué)者的C語言數(shù)據(jù)類型的講解
在 C 語言中，數(shù)據(jù)類型指的是用于聲明不同類型的變量或函數(shù)的一個(gè)廣泛的系統(tǒng)。變量的類型決定了變量存儲(chǔ)占用的空間，以及如何解釋存儲(chǔ)的位模式。2022-04-04
大家好，本篇文章主要講的是C語言二叉樹的遍歷示例介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C語言動(dòng)態(tài)內(nèi)存函數(shù)(malloc、calloc、realloc、free)詳解
在C語言中,動(dòng)態(tài)內(nèi)存函數(shù)是塊重要的知識(shí)點(diǎn),以往,我們開辟空間都是固定得,數(shù)組編譯結(jié)束后就不能繼續(xù)給它開辟空間了,開辟的空間滿了,就不能在開辟空間了,學(xué)習(xí)本文章,我們就可以解決這個(gè)問題,向內(nèi)存申請(qǐng)空間,感興趣的小伙伴跟著小編一起來看看吧2023-08-08
C++實(shí)現(xiàn)評(píng)教管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)評(píng)教管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
利用C++單例模式實(shí)現(xiàn)高性能配置管理器
這篇文章主要為大家詳細(xì)介紹了如何利用C++單例模式實(shí)現(xiàn)高性能配置管理器，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04
C++?shared_ptr智能指針reset()使用示例詳解
這篇文章主要為大家介紹了C++?shared_ptr智能指針reset()使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
C++實(shí)現(xiàn)LeetCode(23.合并k個(gè)有序鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(23.合并k個(gè)有序鏈表),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
c語言函數(shù)棧幀的創(chuàng)建和銷毀過程詳解
我們知道c語言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程，一起看看吧2021-08-08