php专区

 首页 > php专区 > PHP进阶 > 算法 > 合并排序算法解说与例子

合并排序算法解说与例子

分享到:
【字体:
导读:
         摘要:合并算法采用分治法的思路,即问题划分成n个规模较小而结构和原来问题相似的子问题,递归解决这些子问题,然后合并结果,最终得到原来问题的解。合并算法主要分为三个部分,第一个部分是分解,将运来的问题分解成两个包含n/2个元素的数组的排序的问题,然后分别递归调用函数解决这两个数组的排序问题。 ...

合并排序算法解说与例子

合并算法采用分治法的思路,即问题划分成n个规模较小而结构和原来问题相似的子问题,递归解决这些子问题,然后合并结果,最终得到原来问题的解。

合并算法主要分为三个部分,第一个部分是分解,将运来的问题分解成两个包含n/2个元素的数组的排序的问题,然后分别递归调用函数解决这两个数组的排序问题,最后一步,就是将已经排好序的数组重新进行组合,使其成为按序排列的数组。

这三步中代码量较多的就是合并的代码了,合并的问题其实我们也可以把它想象成把两堆已经按从小到大的顺序排好的扑克牌排成一堆扑克牌的问题,每次比较最上面的那个牌,小的就拿走放到输出堆中,重复这个比较过程直到某一堆牌为空,然后把另外一堆牌直接放到输出堆中这个比较过程就结束了,想清楚了了这个过程的话理解代码就不难了。

		//将两个数组按照顺序重新进行排列
       public static void Merge(int[] rawArray, int firstIndex, int middleIndex, int lastIndex)
       {
           //把middle指向的元素划分到前面的一个数组去
             int firstArrayCount = middleIndex - firstIndex + 1;
           int secondArrayCount = lastIndex - middleIndex;
           int[] firstArray = new int[firstArrayCount];
           int[] secondArray = new int[secondArrayCount];
           //将原来数组的元素分别复制到两个分开的数组当中去
            for (int i = 0; i 
  
  	

看懂了上面的合并,下面这个递归调用就没什么了,函数将数组进行拆分,然后递归调用函数进行子数组的排序,子数组排序完成后调用合并函数将数组进行合并。

/// 
/// 
/// 
/// 需要排序的数组
/// 左边界
/// 右边界
public static void MergeSort(int[] rawArray, int firstIndex, int lastIndex)
{
    if (firstIndex 
    
    

合并排序体现的主要是一个将问题进行拆分解决的思路,通过递归调用函数来解决子问题,最后合并结果,从而得到原问题的解。

身边很多人在学数据结构和算法的时候对算法的语言有着特殊的要求,个人觉得学习算法学习的是一种解决问题的思路,而不是具体的代码实现,this is the point….

本文地址:http://www.nowamagic.net/librarys/veda/detail/248,欢迎访问原出处。

合并排序算法解说与例子
分享到:
JavaScript排序算法之冒泡排序
JavaScript排序算法之冒泡排序 冒泡排序,是指计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点: “编程复杂度”很低,很容易写出代码; 具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,而堆排序、快...
计算机编程中一些重要的算法
计算机编程中一些重要的算法 下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。(注:本篇文章并非翻译,其中的算法描述大部...
  •         php迷,一个php技术的分享社区,专属您自己的技术摘抄本、收藏夹。
  • 在这里……