欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

MergeSort(归并排序)原理及C++代码实现

程序员文章站 2022-05-29 07:58:28
归并排序利用分治策略进行排序。原理如下 分解:分解待排的n个元素的序列成个具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 归并排序的时间复杂度是θ(nlgn)。 归并排序是稳定排序之一。 归并排序不是原址排序,在合并阶段需要申 ......

归并排序利用分治策略进行排序。原理如下

分解:分解待排的n个元素的序列成个具n/2个元素的两个子序列。

解决:使用归并排序递归地排序两个子序列。

合并:合并两个已排序的子序列以产生已排序的答案。

归并排序的时间复杂度是θ(nlgn)。

归并排序是稳定排序之一。

归并排序不是原址排序,在合并阶段需要申请额外的数组空间。

代码如下:(仅供参考)

1 void mergesort(int * const begin, int * const end) {
2     if (begin + 1 >= end)
3         return ;
4     int m = (end - begin) / 2;
5     mergesort(begin, begin + m);
6     mergesort(begin + m, end);
7     merge(begin, begin + m, end);
8 }
 1 //不使用哨兵的版本,需判断边界条件
 2 void merge(int * const first, int * const mid, int * const last) {
 3     vector<int> left(first, mid);
 4     vector<int> right(mid, last);
 5 
 6     int i = 0, j = 0, k = 0;
 7     while (i != left.size() && j != right.size()) {
 8         if (left[i] <= right[j]) {
 9             *(first + k) = left[i++];
10         } else {
11             *(first + k) = right[j++];
12         }
13         ++k;
14     }
15     while (i != left.size()) {
16         *(first + k) = left[i++];
17         ++k;
18     }
19     while (j != right.size()) {
20         *(first + k) = right[j++];
21         ++k;
22     }
23 }
 1 //使用哨兵来简化代码
 2 void merge(int * const first, int * const mid, int * const last) {
 3     vector<int> left(first, mid);
 4     vector<int> right(mid, last);
 5     left.push_back(int_max);       //哨兵int_max必须总是比较中的较大者
 6     right.push_back(int_max);      //即待排序的值必须比int_max小
 7 
 8     int i = 0, j = 0;
 9     for (int k = 0; k < last - first; ++k) {
10         if (left[i] <= right[j]) {
11             *(first + k) = left[i++];
12         } else {
13             *(first + k) = right[j++];
14         }
15     }
16 }