排序算法之归并算法

/*
    本例拟在实现排序算法的归并算法,归并算法遵循分治法的思想
    归并算法:
    归并算法主要用来合并两个已经排好序的序列。用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] * 输入:

排序算法 归并算法(递归+非递归)

部分理论和图来自:http://www.cnblogs.com/jingmoxukong/p/4308823.html  (侵删) 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并排序的基本思想 将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,

算法导论第二章C++实现归并算法排序

归并算法排序的思想算法导论中讲的还算比较清楚. #include<iostream> using namespace std; void guibing(int *_array,int p,int q,int r); void merge_sort(int *_array,int p,int r); int main() { int a[8]={2,4,5,7,1,2,3,6}; int j1=0; int j2=7; merge_sort(a,j1,j2); int i=0; for(;i&

排序算法 - 归并算法

在实际应用当中,对于数据较大的输入,归并排序是比较快的一个算法.该算法采用的是分治法的思想. 原理:将数据分开排序,然后进行合并,最后形成一个排好的序列. 将其合并输出,如下图所示: 代码实现如下: /** * 归并排序 * * @author Deters * @date 2019/10/12 */ public class MergeSort { /** * 归并 */ private static void merge(Integer[] array, int start, int end

必须知道的八大种排序算法【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)的算法.而归并算法之所以快的原因在于它用了分治的思想,现实生活中有很多需要用到分治思想解决的问题,下面就举两个例子. 问题一: 给定一个整数数组和任意整数,找到数组中是否有两数的和等于给定的整数. 这个问题如果采用穷举法,则大致思路是这样:首先数组的第一个元素与数组剩下的元素相加,看是否有对应的结果.然后再数组第二个元素与除第一个元素和第二个元素本身之外的元素相加... 后面的操作一次类推.很容易得到时间复杂度为:

十种常见的排序算法,面试算法必考

1.冒泡排序 已知一组无序数据a[1].a[2].……a[n],需将其按升序排列.首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变.再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变.再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值.这样处理一轮后,a[n]的值一定是这组数据中最大的.再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的.再对a[1]~a[n-2]以相同方

归并算法的非递归实现

任何的递归算法都可以转换为非递归算法,而且一般来说递归算法的效率比非递归算法的效率低.但是为啥会有递归算法呢,是因为递归算法看起来思路清晰,而且代码简洁.接下来我主要介绍下归并算法的非递归实现. 主要思想:对于归并算法的非递归实现,我们可以沿着递归实现的逆向方向去思考,递归的思想是自顶向下,将待排序序列不断分解,然后再归并.而非递归的思想就是自底向上,先两两归并,然后再4个4个一起归并,再8个.....在这个过程中一定要注意尾部数据的处理,因为序列的长度不一定就是归并长度的整数倍. 代码实现:

归并算法

归并算法:实现排序. 归:递归.并:合并. 如何递归,如何合并? 使用归并算法的优点:算法的时间复杂度和空间复杂度低. import java.util.Arrays; /** * 归并排序程序,要求输入10个整数,输出排序结果 * Created by ZL on 2016/8/19. */ public class Fourth { public static void main(String[] args) { int[] arr = {9,8,7,6,5,4,3,2,1,0}; sort