溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
定義：歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
簡單的來說，歸并排序主要分為三步，一是對數組的劃分，二是對數組的排序，三是對數組的合并。劃分的大小是可以隨自己的想法而設置，但是一般都是以2為單位，這樣最小的一組的排序就比較方便。
具體一個簡單的例子：
設有數列{6，202，100，301，38，8，1}
初始狀態：6,202,100,301,38,8,1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數：4；
總的比較次數為：3+4+4=11；
逆序數為14；
在利用算法實現的時候，需要利用遞歸的思想，函數的入口是整個數組，不斷進行劃分，直到劃分的數組只剩下一個或兩個元素為止，對這一組進行排序后，再按原來劃分的大小還原并排序，這里利用一個新的數組比較方便，將兩個排序后的數組，再從小到大一個一個放入新的數組。
具體代碼：
#include<iostream>
#include<algorithm>
using namespace std;
void merge(int *data,int start,int end,int *result)
{
int left_length = (end - start + 1) / 2 + 1;
int left_index = start;
int right_index = start + left_length;
int result_index = start;
while(left_index<start + left_length && right_index <end + 1) //store data into new array
{
if(data[left_index] <= data[right_index])
result[result_index++] = data[left_index++];
else
result[result_index++] = data[right_index++];
}
while(left_index < start + left_length)
result[result_index++] = data[left_index++];
while(right_index <end+1)
result[result_index++] = data[right_index++];
}
void merge_sort(int *data,int start,int end,int *result)
{
if(1 == end - start) //last only two elements
{
if(data[start] > data[end])
{
int temp = data[start];
data[start] = data[end];
data[end] = temp;
}
return;
}
else if (end == start)
return; //last one element then there is no need to sort;
else{
//continue to divide the interval
merge_sort(data, start, (end - start + 1) / 2 + start, result);
merge_sort(data, (end - start + 1) / 2 + start + 1, end, result);
//start to merge sorted data
merge(data, start, end, result);
for (int i = start; i <= end;++i)
{
data[i] = result[i];
}
}
}
//example
int main()
{
int data[] = {5,3,6,7,3,2,7,9,8,6,34,32,5,4,43,12,37};
int length = 17;
int result[length];
cout << "before sorted:"<<'\n';
for (int i = 0; i < length;i++)
cout << data[i]<<' ';
cout << '\n'
<< "after sorted:"<<'\n';
merge_sort(data, 0, length - 1, result);
for (int i = 0; i < length;i++)
cout << result[i]<<' ';
return 0;
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
