归并排序

最近的算法课,上得我是一脸懵逼,大一学过归并排序,现在也忘得差不多了,现在来回顾一下。


1.关于归并
这是归并排序中很重要的一个步骤,一定要耐心的看明白。如果给定两个已经排好序的数组,A=[1,3,5],B=[2,4], 现在要将两个数组合并成一个有序数组,你会怎么做?
1.开辟一个长度为10的数组C

  1. 先在A,B数组中各取第一个元素进行比较,将小的元素放入数组C中;
    3.取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较,重复上述比较过程,直到某个数组被先排完;
    4.将另一个数组剩余元素写入c数组,合并排序完成。
    代码:
public class MergeSort {
    @Test
    public void merge() {
        int[] A = {1, 2, 3};
        int[] B = {2, 4, 5};
        int i1 = 0, i2 = 0, i3 = 0;
        int[] C = new int[6];
        while (i1 < A.length && i2 < B.length) {
            if (A[i1] <= B[i2]) {
                C[i3++] = A[i1++];
            } else {
                C[i3++] = B[i2++];
            }
        }
        while(i1<A.length){
            C[i3++] = A[i1++];
        }
        while(i2<B.length){
            C[i3++]=B[i2++];
        }
        for(int i=0; i<C.length;i++){
            System.out.print(C[i]+" ");
        }
    }

运行结果:
分享图片

未完待续...(可以参考https://www.jianshu.com/p/33cffa1ce613)

相关文章
相关标签/搜索