排序算法——归并排序

关键词：

/**
 * 归并排序
 * @author DHH
 *
 */
public class Select extends Example {
    /**
     * 归并排序
     */
    //缓存数组用来排序的时候存储排序前的位置。
    private static Comparable[] b;
    /**
     * 排序方法，对外接口
     */
    public void sort(Comparable[] a){
        b=new Comparable[a.length];
        sort( a,0,a.length-1);
    }
    /**
     * 分治中的分方法，并且递归安排好治的顺序
     * @param a
     * @param lo
     * @param hi
     */
    public void sort(Comparable[] a,int lo,int hi){

        int mid=(hi+lo)/2;
        
        if(hi<=lo) return;
        //mid+1为起步，因为两位数的时候java向下取整，会有mid=lo的情况，无限递归。
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        sort(a,lo,mid,hi);
    }
    /**
     * 分治中的治方法，
     * @param a
     * @param lo
     * @param hi
     */
    public void sort(Comparable[] a,int lo,int mid,int hi){
        //mid必须是+1为起步，因为数组只有两位数时mid可能会等于lo，有相同数字相比的情况，无法正常排序。
        int i=lo;
        int j=mid+1;
        //迁移数组
        for(int k=lo;k<=hi;k++){
            b[k]=a[k];
        }
        
        for(int k=lo;k<=hi;k++){
            //
            if(i>mid){
                a[k]=b[j++];
            }else if(j>hi){
                a[k]=b[i++];
            }else if(b[i].compareTo(b[j])>0){
                a[k]=b[i++];
            }else{
                a[k]=b[j++];
            }
        }
    }
    
    
    
    /**
     * 测试方法
     * @param args
     */
    public static void main(String[] args) {
        DATA[] dataArray=new DATA[15];
        dataArray[0]=new DATA(16);
        dataArray[1]=new DATA(6);
        dataArray[2]=new DATA(15);
        dataArray[3]=new DATA(8);
        dataArray[4]=new DATA(11);
        dataArray[5]=new DATA(23);
        dataArray[6]=new DATA(75);
        dataArray[7]=new DATA(4);
        dataArray[8]=new DATA(11);
        dataArray[9]=new DATA(60);
        dataArray[10]=new DATA(71);
        dataArray[11]=new DATA(24);
        dataArray[12]=new DATA(56);
        dataArray[13]=new DATA(31);
        dataArray[14]=new DATA(42);
        System.out.println(Arrays.toString(dataArray));
        Select select=new Select();
        select.sort(dataArray);
        System.out.println(Arrays.toString(dataArray));
    }
}

排序算法6——归并排序

归并排序（MergeSort），又称二路归并排序，是指将一个数组一分为二，对每一个子数组递归排序，最后将排好的子数组合并为一个有序数组的过程。归并排序，是“分治法”应用的完美实现。FromWikipedia：https://en.wikipedia.org/wiki/Me... 查看详情

八大排序算法之七-归并排序

归并类的排序算法归并：将两个或两个以上的有序表组合成一个新的有序表。内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录有序的序列。归并排序是建立在归并操作上的一种有... 查看详情

排序算法归并排序

...题，然后再合并这些子问题的解来建立原问题的解。归并排序操作分解：将待排序的包含n个元素的序列分解为各含n/2个元素的子序列解决：使用归并排序递归的排序两个子序列合并：合并两个子序列以产生已排序的答案归并排... 查看详情

[算法]——归并排序（mergesort）

归并排序（MergeSort）与快速排序思想类似：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递... 查看详情

算法：归并排序

算法：归并排序写在前面　　归并排序算法是基于一个简单的归并操作：合并两个有序数组来形成一个更大的有序数组。　　提炼归并的思想，归并排序就是将一个无序数组先划分成两个部分(递归地)，对其分别排序，然后再进... 查看详情

算法排序归并排序

正文之前归并排序(Mergesort)，是建立在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由约翰冯诺依曼首次提出，该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。????????????????????????——Wikiped... 查看详情

排序算法之归并排序（java）(代码片段)

通过Java实现归并排序归并排序介绍归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法的一个非常典型的应用。归并算法的主要步骤将待排序的序列分成两个子序列将子序列合并并排序重复一二... 查看详情

归并排序算法

归并排序讲解(经典)：http://blog.csdn.net/jianyuerensheng/article/details/51262984http://blog.51cto.com/flyingcat2013/1281026归并排序：归并排序是基于一种被称为“分治”（divideandconquer）的策略。归并排序就是利用归并的思想实现的排序方法。而且... 查看详情

排序算法中——归并排序和快速排序(代码片段)

冒泡排序、插入排序、选择排序这三种算法的时间复杂度都为$O(n^2)$，只适合小规模的数据。今天，我们来认识两种时间复杂度为$O(nlogn)$的排序算法——归并排序（MergeSort）和快速排序（QuickSort），他们都用到了分治思想，非常... 查看详情

看动画学算法之:排序-归并排序(代码片段)

目录简介归并排序的例子归并排序算法思想归并排序的java实现归并排序的时间复杂度简介归并排序简称Mergesort是一种递归思想的排序算法。这个算法的思路就是将要排序的数组分成很多小的部分，直到这些小的部分都是已排序... 查看详情

排序算法——归并排序

三、归并排序（MergeSort）　/***归并排序的驱动程序*/voidmergeSort(vector<int>&a){vector<int>tmpArray(a.size());mergeSort(a,tmpArray,0,a.size()-1);}/***进行递归调用的内部方法*a为待排序数组*tmpArray为存放归并排序结果的数组*left为子数组... 查看详情

排序算法之归并排序(代码片段)

    前面几篇介绍的选择排序、插入排序、冒泡排序等都是非常简单非常基础的排序算法，都是用了两个for循环，时间复杂度是平方级别的。本篇介绍一个比前面稍微复杂一点的算法：归并排序。归并排序算法里面... 查看详情

排序算法

1、归并排序要将一个数组排序，可以先（递归地）将它分成2半分别进行排序，然后将结果归并起来。自顶向下的归并排序：先将数组划分2部分，分别递归调用子数组进行排序，最后将子数组归并为最终的结果。自底向上的归并... 查看详情

排序算法系列：归并排序算法(代码片段)

概述上一篇我们说了一个非常简单的排序算法——选择排序。其复杂程序完全是冒泡级的，甚至比冒泡还要简单。今天要说的是一个相对比较复杂的排序算法——归并排序。复杂的原因不仅在于归并排序分成了两个部分进行... 查看详情

排序算法——二路归并排序

二路归并排序主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。二... 查看详情

递归分治算法-归并排序算法

...算法通常用到递归算法来实现，故标题为递归分治。归并排序算法归并就是将两个或两个以上的有序表合并成一个新的有序表。归并排序就是将无序的待排序的序列分解成若干个有序的子序列，并把有序子序列合并为整体有序序... 查看详情

排序算法--mergesorting--归并排序--mergesort--归并排序(代码片段)

1.基本思想 　　 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段... 查看详情

算法_归并排序

　　归并排序的基本思想是:将两个已经有序的数组,归并成为更大的有序数组.这种操作称为归并排序.要让一个数组排序,可以先递归的把它分成两半分别排序,然后将结果归并起来.归并排序能够保证对一个任意长度为N的数组排序... 查看详情