经典排序之 归并排序

Author: bakari  Date: 2012.7.30

排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为归并排序。

归并排序是分治法最好的应用,先将一个大的问题分解成小的问题,然后着重去解决小的问题,小问题一解决大问题也就自然而然地解决了。

所以分治法的具体思路就出来了:

将一个数组序列按分为两个序列,序列1和序列2 ,从首元素开始比较,小的元素插入到另一个容器,知道其中一个序列排列完,在把另外的序列插入到该容器的后面,但前提是两个序列事先应该排好序。排好一趟之后再扩大序列区间,随着小问题的解决,大问题也就解决了。

废话不多说,见代码:先看类的定义:

 1 /***********************************************************
 2  *  Author: bakari Date: 2012.7.30
 3  *  合并排序
 4  *  合并排序的宗旨是将两个已经排好序的序列重新归并为一个序列
 5  *  算法的关键点就在于确定合并的基数,即每一次合并元素的数量
 6  ***********************************************************/
 7 class MegerSort
 8 {
 9     int len;
10     vector<int> MegerList;
11     vector<int> ReplaceList;
12 public:
13     MegerSort(vector<int> _list,int len);
14     void Meger_Sort(int index);
15     void FindIndex();       
16     void Print();
17 };

下一步需要找到分治的基数,就是序列区间的大小,从 1 开始,如下:

 1 void MegerSort::FindIndex()
 2 {
 3     int ix = 1;
 4     while(ix < len)
 5     {
 6         Meger_Sort(ix);
 7         for (int i = 0; i != len;++i)
 8             MegerList[i] = ReplaceList[i];
 9         ix = ix * 2;
10     }
11 
12 }

下面就是排序的算法:

 1 void MegerSort::Meger_Sort(int index)
 2 {
 3     int i1 = 0;          //序列1的起始元素
 4     int k = 0;
 5     while(i1 + index <= len){
 6 
 7         int i2= i1 + index;     //序列2的起始元素
 8         int j1 = i2 - 1;        //序列1的末端元素
 9         int j2 = (i2 + index - 1) < (len -1) ? i2 + index -1 : len - 1; //序列2的末端位置
10         while (i1 <= j1 && i2 <= j2)
11         {
12             if (MegerList[i1] < MegerList[i2])
13                 ReplaceList[k++] = MegerList[i1++];       //将小的元素放入另一个容器
14             else ReplaceList[k++] = MegerList[i2++];
15         }
16         if (i1 > j1)                                      //如果序列1排列完
17         {
18             while (i2 <= j2)                              //进行序列2的排列
19                 ReplaceList[k++] = MegerList[i2++];       
20         }
21         if (i2 > j2)                                      //和上面相反
22         {
23             while (i1 <= j1)
24                 ReplaceList[k++] = MegerList[i1++];
25         }
26         i1 = j2 + 1;
27     }
28 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WindCoder

求十个数中最大值和最小值-C++

3191
来自专栏C/C++基础

C/C++结构体初始化与赋值

结构体是常用的自定义构造类型,是一种很常见的数据打包方法。结构体对象的初始化有多种方式,分为指定初始化、顺序初始化、构造函数初始化。假如有如下结构体。

1882
来自专栏Python数据科学

Python 内建函数大全

Python 解释器内置了许多函数和类型,列表如下(按字母排序)(省略了几个我没用过或者不常用的)。

2543
来自专栏函数式编程语言及工具

泛函编程(16)-泛函状态-Functional State

    初接触泛函状态觉着很不习惯。主要是在使用State数据类型时很难理解其中的原理,特别是泛函状态变迁机制(state transition mechani...

21110
来自专栏Python

python ——面向对象进阶

1.staticmethod和classmethod staticmethod  静态方法: 让类里的方法,直接被类调用,就像正常的函数一样 宝宝,男 博博,女...

2017
来自专栏java一日一条

Java内部类

这样看起来,类Draw像是类Circle的一个成员,Circle称为外部类。成员内部类可以无条件访问外部类的所有成员属性和成员方法(包括private成员和静...

961
来自专栏Young Dreamer

正则学习笔记——重复、贪婪与懒惰

1.贪婪与懒惰 贪婪与懒惰的适用情况是针对重复的情况; 重复的限定符: * 重复>=0次 + 重复>=1次 ? 重复0或1次 {n} 重复n次...

1936
来自专栏北京马哥教育

python模块之re正则表达式详解

正则表达式是一种小型的、高度专业化的编程语言,并不是python中特有的,是许多编程语言中基础而又重要的一部分。在python中,主要通过re模块来实现。这篇文...

4069
来自专栏黑泽君的专栏

c语言基础学习07_指针

=============================================================================

2100
来自专栏mukekeheart的iOS之旅

OC学习2——C语言特性之函数

1、OC是在C语言的基础上进行扩展的,在OC中直接用C语言进行coding也是可以通过编译的。因此,函数定义的语法格式如下: 函数返回值类型 函数名(形参列表...

3117

扫码关注云+社区

领取腾讯云代金券