排序算法之归并算法

/*
    本例拟在实现排序算法的归并算法,归并算法遵循分治法的思想
    归并算法:
    归并算法主要用来合并两个已经排好序的序列。用Merge(A,p,q,r)来实现合并,
    其中A代表数组,A[p,q]和A[q+1,r]A的两个子数组,且两个数组都已经排好序,归并算法
    就是将这两个子数组合并成一个排好序的数组并替代当前的数组A[p,r]。
*/
public class Merge
{
    public static void main(String[] args)
    {
        int[] a = {1,2,3,4,5,7,9,11,6,8,10,12,13,14,15,16};
        merge(a,4,7,11);
        for(int i=0; i<a.length; i++)
        {
            System.out.print(a[i]);
        }
    }

    public static int[] merge(int[] a, int leftStart, int leftEnd, int rightEnd)
    {
        int left_length = leftEnd - leftStart + 1; //左数组的长度
        int right_length = rightEnd - leftEnd; //右数组的长度

        int[] left = new int[left_length + 1];  //构建左数组的副本,长度加1,用来存放标志牌
        int[] right = new int[right_length + 1]; //构建右数组的副本,长度加1,用来存放标志牌

        for(int i=0; i<left_length; i++)
        {
            left[i] = a[leftStart + i];    //往左数组的副本里拷贝数据
        }
        for(int i=0; i<right_length; i++)
        {
            right[i] = a[leftEnd + i + 1];  //往右数组的副本里拷贝数据
        }

        left[left_length ] = 10000;          //左数组最后一个数放一个大数,用作结束的标志
        right[right_length ] = 10000;        //右数组的最后一个数放一个大数,用作结束的标志

        int i=0;    //初始化左右两个数组的下标
        int j=0;

        /*
            从数组的leftStart到rightEnd区间内开始循环比较左右两个数组内数值的大小
            如果左数组的某个值小,就把值放入对应的a数组内,左数组的数组下标加1
            如果右数组的某个值小,就把值放入对应的a数组内,右数组的数组下标加1
        */
        for(int k=leftStart; k<rightEnd; k++)
        {
            if(left[i] < right[j])
            {
                a[k] = left[i];
                i = i + 1;
            }else
            {
                a[k] = right[j];
                j = j + 1;
            }
        }
        return a;
    }
}
时间: 04-11

排序算法之归并算法的相关文章

算法:归并算法的递归与非递归形式

归并算法是将两个或两个以上的有序表组合成一个新的有序表,它的原理是:假设初始序列含有n个记录,则可以看成是n个有序子序列,两两归并,得到[n/2]个有序子序列,再次归并--不断重复直至归并到长度为n的有序序列,这样的排序方法称为2路归并排序. 实例一:递归形式的2路归并算法 #define MAXSIZE 4 int data[MAXSIZE] = {2,1,0,3}; /* * 功能:将from数组min到max-1下标数据排好序,最后的结果是to[min]...to[max-1] * 输入:

必须知道的八大种排序算法【java实现】(三) 归并排序算法、堆排序算法详解

一.归并排序算法 基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]

由归并算法引申出来的其他问题

前言: 上一节刚讲过归并算法是排序算法中比较少见的一种时间复杂度为:θ(nlgn)的算法.而归并算法之所以快的原因在于它用了分治的思想,现实生活中有很多需要用到分治思想解决的问题,下面就举两个例子. 问题一: 给定一个整数数组和任意整数,找到数组中是否有两数的和等于给定的整数. 这个问题如果采用穷举法,则大致思路是这样:首先数组的第一个元素与数组剩下的元素相加,看是否有对应的结果.然后再数组第二个元素与除第一个元素和第二个元素本身之外的元素相加... 后面的操作一次类推.很容易得到时间复杂度为:

php基于左右值排序的无限分类算法

PHP无限分类[左右值]算法 <?php /** * 基于左右值排序的无限分类算法 * 数据库结果为 CREATE TABLE om_catagory ( CatagoryID int(10) unsigned NOT NULL auto_increment, Name varchar(50) default '', Lft int(10) unsigned NOT NULL default '0', Rgt int(10) unsigned NOT NULL default '0', PRIM

算法学习——分治算法

这是从网上查到的概念资料,先收来~ 一.基本概念 在计算机科学中,分治法是一种很重要的算法.字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并.这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关.问题的规模越小,越容易直接求解,解题所需的计算时间也越少.例如,对于n个

最小生成树(prim算法,Kruskal算法)c++实现

1.生成树的概念 连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树. 生成树是连通图的极小连通子图.所谓极小是指:若在树中任意增加一条边,则将出现一个回路:若去掉一条边,将会使之变成非连通图. 生成树各边的权值总和称为生成树的权.权最小的生成树称为最小生成树. 2.最小生成树的性质用哲学的观点来说,每个事物都有自己特有的性质,那么图的最小生成树也是不例外的.按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点.n-1 条边. 3.构造最小生成树,要解决以下两个问题

转载:算法杂货铺——分类算法之决策树(Decision tree)

作者:张洋 算法杂货铺——分类算法之决策树(Decision tree) 2010-09-19 16:30 by T2噬菌体, 44346 阅读, 29 评论, 收藏, 编辑 3.1.摘要 在前面两篇文章中,分别介绍和讨论了朴素贝叶斯分类与贝叶斯网络两种分类算法.这两种算法都以贝叶斯定理为基础,可以对分类及决策问题进行概率推断.在这一篇文章中,将讨论另一种被广泛使用的分类算法——决策树(decision tree).相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置,因此在实际

[算法学习笔记]算法基础知识

算法基础知识 算法的五大要素 有穷性:算法必须能够在有限个步骤内完成. 确定性:算法的每一步必须有确定的定义. 输入 输出 可行性:算法的每个步骤都必须能分解为基本的可执行操作,每个步骤都必须能在有限时间内完成 循环不变式 循环中的循环不变式可以帮助我们理解算法的正确性.为了证明算法的正确,必须证明循环不变式的三个性质: 1. 初始化:循环不变式在循环开始之前是正确的. 2. 保持:循环不变式在循环的每一次迭代开始之前是正确的. 3. 终止:在循环结束时,不变式会给出一个可以对判断算法是否正确有

[数据结构和算法]折半插入排序算法笔记

/// <summary> /// 步骤: /// 1.记录当前待排元素 /// 2.标记顺序表有序查找区域下界和上界 /// 3.在顺序表有序查找区域中折半查找等待排序元素的位置 /// 4.把顺序表有序查找区域的某些元素后移一位,以空出位置给等待排序的元素 /// 5.在空出的位置填写当前排序元素 /// </summary> /// <param name="elements"></param> static void SqList