快捷導(dǎo)航

C++實(shí)現(xiàn)歸并排序

更新時(shí)間：2020年03月20日 07:47:14 作者：EggyGeDan

這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)歸并排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

定義：歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

簡單的來說，歸并排序主要分為三步，一是對(duì)數(shù)組的劃分，二是對(duì)數(shù)組的排序，三是對(duì)數(shù)組的合并。劃分的大小是可以隨自己的想法而設(shè)置，但是一般都是以2為單位，這樣最小的一組的排序就比較方便。

具體一個(gè)簡單的例子：

設(shè)有數(shù)列{6，202，100，301，38，8，1}

初始狀態(tài)：6,202,100,301,38,8,1

第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3；

第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數(shù)：4；

第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4；

總的比較次數(shù)為：3+4+4=11；

逆序數(shù)為14；

在利用算法實(shí)現(xiàn)的時(shí)候，需要利用遞歸的思想，函數(shù)的入口是整個(gè)數(shù)組，不斷進(jìn)行劃分，直到劃分的數(shù)組只剩下一個(gè)或兩個(gè)元素為止，對(duì)這一組進(jìn)行排序后，再按原來劃分的大小還原并排序，這里利用一個(gè)新的數(shù)組比較方便，將兩個(gè)排序后的數(shù)組，再從小到大一個(gè)一個(gè)放入新的數(shù)組。

具體代碼：

#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;
}