`
foreversunyao
  • 浏览: 218229 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

归并排序-转载

阅读更多

http://seaizon.iteye.com/blog/571153

合并排序
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假 设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个  N/2   个长度为2或1的有序子序列,再两两合并,如此重复,值得得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。

  例如数组A有7个数据,分别是: 49   38   65  97   76   13   27,那么采用归并排序算法的操作过程如图7所示:

  初始值                 [49]   [38]   [65]   [97]   [76]   [13]   [27]

  看成由长度为1的7个子序列组成

  第一次合并之后         [38     49]    [65    97]   [13     76]   [27]

看成由长度为1或2的4个子序列组成

  第二次合并之后         [38     49      65    97]   [13     27     76]

看成由长度为4或3的2个子序列组成

  第三次合并之后         [13     27      38    49     65      76    97]

                          图6    归并排序算法过程图

合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现,形式上较为简单,但实用性很差。

合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数

是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一

X

规律,当有N个子序列时可以推断出合并的次数是X(2  >=N,符合此条件的最小那个X)。
*/

Java代码
  1. public   static   void  mergeSort( int [] array, int  low, int  height){  
  2.         if (low>=height) return ;  
  3.         int  mid = (low+height)/ 2 ;  
  4.         mergeSort(array,low,mid);  
  5.         mergeSort(array,mid+1 ,height);  
  6.         merge(array,low,mid,height);  
  7.     }  
  8.       
  9.     public   static   void  merge( int [] array, int  low, int  mid, int  height){  
  10.         int  i,j,h,k;  
  11.         int [] temp =  new   int [array.length];  
  12.         i=low;  
  13.         h=low;  
  14.         j=mid+1 ;  
  15.           
  16.         while (h<=mid&&j<=height){  
  17.             if (array[h]<array[j]){  
  18.                 temp[i] = array[h];  
  19.                 h++;  
  20.             }else {  
  21.                 temp[i] = array[j];  
  22.                 j++;  
  23.             }  
  24.             i++;  
  25.         }  
  26.           
  27.         if (j>height){  
  28.             for (k=h;k<=mid;k++){  
  29.                 temp[i] = array[k];  
  30.                 i++;  
  31.             }  
  32.         }else {  
  33.             for (k=j;k<=height;k++){  
  34.                 temp[i] = array[k];  
  35.                 i++;  
  36.             }  
  37.         }  
  38.         for (k=low;k<=height;k++){  
  39.             array[k] = temp[k];  
  40.         }  
  41.     } 
分享到:
评论

相关推荐

    python数据结构与算法详解与源码

    5-14 归并排序时间复杂度及排序算法复杂度对比 5-15 二分查找 5-16 二分查找时间复杂度 六、树和树的算法 6-01 树的概念 6-02 二叉树的概念 6-03 二叉树的广度优先遍历 6-04 二叉树的实现 6-05 二叉树的先序...

    排序算法总结(转载)

    本文将对几种常见的排序算法进行总结,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、拓扑排序、锦标赛排序以及基数排序。 **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过不断...

    剑指Offer – 面试题51. 数组中的逆序对(归并排序,求逆序对)

    1. 题目 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。...2. 归并排序 详见 LeetCode 315. 计算右侧小于当前元素的个数(二叉查找树&二分查找&归并排序逆序数总结) 方法

    [转载]nlogn的最长子序列算法.rar_最长 排序_最长子序列

    排序可以使用快速排序、归并排序等高效算法,这里的关键在于排序后的序列可以帮助我们找到最长子序列。 2. **记录最大值**:创建一个新的数组,用于存储每个位置的最长子序列的结束点。数组的初始值为1,表示每个...

    北京交通大学-数据结构925-13年-18年考研真题(转载).rar

    7. **排序和查找**:除了上述数组的排序算法,还有其他高级排序算法如归并排序、希尔排序、快速排序的变种等。查找算法有顺序查找、二分查找、哈希查找等,它们的效率分析是重要考点。 8. **动态规划**:在数据结构...

    blog:博客,想法,笔记

    归并排序 二分法 deep TypeScript ts效能开发【Recent update】 h5c3 h5开发坑点小总结:fire: h5适配 开源项目 wechatApp-template refactor-boilerplate omim-tag vscode有趣的插件 修改vscode背景图 自编杂文...

    考研数据结构算法C语言实现最新代码.pdf

    在算法方面,考研中常见的有排序算法(如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等)、查找算法(如顺序查找、二分查找、哈希查找)、图的遍历算法(如深度优先搜索DFS和广度优先搜索BFS)、字符...

    Java面试资料大集合

    - **排序算法**:冒泡、选择、插入、快速、归并等,以及时间复杂度分析。 - **查找算法**:二分查找,哈希查找。 - **常用数据结构**:栈、队列、链表、树、图等。 通过阅读《Java常见面试题.doc》、《Java面试...

Global site tag (gtag.js) - Google Analytics