Java教程

数据结构与算法之归并排序

本文主要是介绍数据结构与算法之归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

/*
 * 递归之归并排序 
 * 归并排序就是将两个有序的数组,合到一起,得到一个新的有序数组的过程
 * 算法分析:首先拿a的第一个元素跟b的第一个元素比较,a的大,那么把b的元素放到新的数组c上
 * 然后再拿a的第一个元素跟b的第二个元素比较,a的元素小,那么就把a的第一个元素放到数组c上
 * 依次类推:当组数a的所有元素都被放到c中时,可以直接把b中剩下的元素直接放到c中,反之同理
 */
public class RecursiveMerge {

    public static void main(String[] args) {
        
        int[] a = {3,5,7,9,18,20,25,28,30,54,67,87,98};
        int[] b = {2,4,6,7,9,12,15,17,19,23,26,67};
        int[] c = new int[a.length + b.length];
        merge(a, b, c);
        for(int cv : c){
            System.out.print(cv +",");
        }
    }
    
    private static void merge(int[] a, int[] b, int[] c){
        int ai = 0; int bi = 0; int ci = 0;
        //当数组a或者数组b中有一个数组的数据已经被merge完了的时候,退出循环
        while(ai < a.length && bi < b.length){
            if(a[ai] > b[bi]){
                c[ci++] = b[bi++];
            }else{
                c[ci++] = a[ai++];
            }
        }
        //如果是b数组merge完了,那么把a数组剩下的元素放进去
        while(ai < a.length){
            c[ci++] = a[ai++];
        }
        //如果是a数组merge完了,那么把b数组剩下的元素放进去
        while(bi < b.length){
            c[ci++] = b[bi++];
        }
    }

}
 

//运行结果如下:

2,3,4,5,6,7,7,9,9,12,15,17,18,19,20,23,25,26,28,30,54,67,67,87,98,

这篇关于数据结构与算法之归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!