文档章节

归并排序 Merge sort

fokYaland
 fokYaland
发布于 2015/06/04 17:27
字数 742
阅读 12
收藏 0
是一种简单的排序方法。时间复杂度为  O(N*logN)

思想:归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 分治法(Divide and Conquer)的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

可以看出合并有序数列的效率是比较高的,可以达到 O(n)

解决了上面的合并有序数列问题,再来看归并排序,基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?

可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为 O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

public   class   MergeSort {
       public   static   final   int   CUTOFF   = 11;

       public   static   void   main(String[] args) {
               //   TODO   Auto-generated method stub
               int [] a;
               int   n = 300;
               // 生产随机数组
            a =   new   int [n];
            Random rand =   new   Random();
               for   (   int   i = 0; i < a.   length ; i++) {
                  a[i] = rand.nextInt(n);
            }
               //a = new int [] {33,10,80};
             println(a);

               long   s = System. nanoTime();
               int [] b = mergeSort(a);
               long   dur = System. nanoTime() - s;
             println(b);
            System.   out .println(dur);

      }

       public   static   int [] mergeSort(   int [] a) {
               int [] tmp =   new   int [a.   length ];
             split(a, tmp, 0, a. length -1);
               return   tmp;
      }

       public   static   void   split( int [] a,   int [] tmp,   int   left,   int   right) {
               //System.out.println(left+","+right);
               if   (left < right) {
                     int   center = (left + right) / 2;
                     //System.out.println(center);
                   split(a, tmp, left, center);
                   split(a, tmp, center + 1, right);
                   merge(a,tmp,left,center+1,right);
            }
               //System.out.println("返回");
      }
      public   static   void   merge( int [] a, int [] tmp, int   lPos, int   rPos, int   rEnd){
       //System.out.println("merge:"+lPos+","+rPos+","+rEnd);
       int   lEnd = rPos -1;
       int   tPos = lPos;   
       int   leftTmp = lPos;
       while (lPos <= lEnd && rPos <= rEnd){
               if (a[lPos] <= a[rPos]){
                  tmp[tPos++] = a[lPos++];
            }   else {
                  tmp[tPos++] = a[rPos++];
            }           
      }
      
       while (lPos <= lEnd){
            tmp[tPos++] = a[lPos++];
      }
      
       while (rPos <= rEnd){
            tmp[tPos++] = a[rPos++];
      }
       // copy the tmpArr back cause we need to change the arr array items.
       for   ( ; rEnd >= leftTmp; rEnd-- )
            a[rEnd] = tmp[rEnd];
      
    }

       public   static   void   println( int [] a) {
            System.   out .print(   "[" );
               for   (   int   i = 0; i < a.   length ; i++) {
                  System.   out .print(a[i]);
                     if   (i != a.   length   - 1)
                        System.   out .print(   "," );
            }
            System.   out .println(   "]" );
      }

}











本文转载自:http://blog.csdn.net/yanliang1/article/details/17127399

fokYaland
粉丝 4
博文 68
码字总数 3062
作品 0
东城
私信 提问
stl-stable_sort源码学习笔记

前几天,一个新同事前来询问算法stl-stablesort的情况。由于离上次研读stl源码时间久已(两三年前的事儿了),有些细节笔记模糊了。所以就找了sgi-stl和ms-stl俩版本,重新复习一遍其中的stl...

huangjunkun
2011/11/07
0
0
MIT Introduction to Algorithms 学习笔记(四)

lecture 3 Insertion Sort, Merge Sort 1.(插入排序)Insertion sort def InsertSort(L): if(len(L) == 0 or len(L) == 1): return L tmp = 0 for i in range(1,len(L)): for j in range(i,0,......

hyaicc
2015/12/21
31
0
我最喜欢的排序算法——快速排序和归并排序

申明:此博文转自他人,感觉不错特转载供大家分享 摘要:一般评判排序算法的标准有时间代价,空间代价和稳定性。本文主要讨论性质相对比较好且作者喜欢的快速排序算法和归并排序算法,并对此这...

mjrao
2012/03/23
0
0
C++ 归并排序 求高手解答

算法导论 归并排序 #include using namespace std; void MERGE(int *A,int p,int q, int r); void MERGE_SORT(int *A,int p,int r); int main() { int A[21]; int i,n; cout<<"请输入需要排序......

hjhomw
2015/07/14
131
2
几种常见排序算法

几种常见排序算法 标签: algorithms [TOC] 本文介绍几种常见排序算法(选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序),对算法的思路、性质、特点、具体步骤、java实现以及t...

brianway
2016/05/08
133
2

没有更多内容

加载失败,请刷新页面

加载更多

适合钱包应用开发的ERC20代币数据集

Erc20Tokens数据集包含超过1000种主流的以太坊ERC20代币的描述数据清单和图标,可用于钱包等区块链应用的开发,支持使用Java、Python、Php、NodeJs、C#等各种开发语言查询主流ERC20代币的相关...

汇智网教程
32分钟前
1
0
micro微服务 基础组件的组织方式

micro微服务 基础组件的组织方式 简介 micro是go语言实现的一个微服务框架,该框架自身实现了为服务常见的几大要素,网关,代理,注册中心,消息传递,也支持可插拔扩展。本本通过micro中的一...

魂祭心
59分钟前
4
0
简单的博客系统(三)使用Django的后台管理功能

Django新建项目和应用后,自带有后台管理功能,可直接使用 创建后台管理员账户 (demosite) E:\PycharmProjects\demosite>python manage.py createsuperuserUsername: adminEmail address:...

ZeroBit
今天
3
0
The /usr/local/mysql/data directory is not owned by the 'mysql' to '_mysql' user

20190720 经过前两天折腾环境,重装了 apache 和 mysql 之后,今天调试程序是突然发现,本机的 mysql 起不来了! 在启动面板上,显示有这样一行小字 (抱歉!光顾着解决问题,没有记录下来图片...

wwzzhh166
今天
4
0
centos安装增强功能出现kernel headers not found for target kernel解决办法

最近新安装一个centos虚拟机,在安装增强功能的时候出现了,kernel headers not found for target kernel的错误。特记下我的解决方案。 1.update kernel yum update kernel -y 2.Install the...

mbzhong
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部