首页 / 软件开发 / 数据结构与算法 / 数据结构之归并排序（merging sort） 详解

数据结构之归并排序（merging sort） 详解2015-10-10归并排序（merging sort）: 包含2-路归并排序, 把数组拆分成两段, 使用递归, 将两个有序表合成一个新的有序表.

归并排序（merge sort）的时间复杂度是O（nlogn）, 实际效果不如快速排序（quick sort）和堆排序（heap sort）,

但是归并排序是稳定排序, 而快速排序和堆排序则不是.

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <iostream>#include <algorithm>#include <iterator>using namespace std;/*参数: SR-输入数组, TR-输出数组, i至m:第一段有序, m+1至n:第二段有序*//**/void Merge （const std::vector<int> SR, std::vector<int>& TR, int i, int m, int n）{int j , k;for （j=m+1, k=i; i<=m && j<=n; ++k） {if （SR[i] < SR[j]）TR[k] = SR[i++];elseTR[k] = SR[j++];}if （i<=m）std::copy（（SR.begin（）+i）, （SR.begin（）+m+1）, TR.begin（）+k）;if （j<=n）std::copy（（SR.begin（）+j）, （SR.begin（）+n+1）, TR.begin（）+k）;}/*参数: SR-输入数组, TR-输出数组, s:起始, t:末尾*/void MSort （const std::vector<int> SR, std::vector<int>& TR, int s, int t）{std::vector<int> tempTR（SR.size（））;if （s == t）TR[s] = SR[s];else {int m = （s+t）/2; //平分SR, SR[s..m]和SR[m+1..t]MSort（SR, tempTR, s, m）; //前半段MSort（SR, tempTR, m+1, t）; //后半段Merge（tempTR, TR, s, m, t）; //排序//copy（TR.begin（）, TR.end（）, ostream_iterator<int>（cout, " "））;//std::cout << std::endl;}}void MergeSort （std::vector<int>& L） {MSort（L, L, 0, L.size（）-1）;}int main （void）{std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49};MergeSort（L）;copy（L.begin（）, L.end（）, ostream_iterator<int>（cout, " "））;std::cout << std::endl;return 0;}

输出:

13 27 38 49 49 65 76 97

作者：csdn博客 Caroline-Wendy