开发技术

算法备忘录之二 — 归并排序

前言

上一篇我们介绍了一种比较快速的排序方法,快速排序。 这次,我们来看另一种的常用排序方法,归并排序。 这个归并排序,虽然说是很常用,一些算法的教科书也经常会出现。 但是,实际工作中,本人似乎没有用过一下下?So, 经常忘记,特此备忘。

思路

说到归并排序之前,先来看一个需求。 现在有两个有序数组a和b,把这两个数组合并成一个新的有序数组c。

这个需求不难,根据人类最原始的本能,暴力法。 假设顺序是从小到大排列,直接从第一个数开始,比较两个数组的元素,哪个小就放入c, 最后再把剩余元素放进c。

talk is cheap, show me the code.

// 合并两个有序数组
public static int[] merge(int[] a, int[] b){
    int[] c = new int[a.length + b.length];
    
    int i = 0, j = 0, k = 0;
    while(i < a.length && j < b.length){
        if(a[i] < b[j]){
            c[k++] = a[i++];
        }else{
            c[k++] = b[j++];
        }
    }
    while(i < a.length){
        c[k++] = a[i++];
    }
    while(j < b.length){
        c[k++] = b[j++];
    }
    
    return c;
}

真-归并排序

归并排序,就是以上的步骤,再加上分治法(是不是感到如此熟悉,快速排序也应用了此思想)。 具体过程是,就是把一个数组,分成两半,再对这两半进行归并排序,直到无法进行。 排序的方式,就是我们上一部分讲的方法了。。。 无法进行的条件,就是数组不能再分,也就是只剩下一个元素了。这时候,数组必然有序,就符合归并排序的条件了。 忘了补充一点,归并排序的时间复杂度是O(nlogn)。

talk is cheap, show me the code.

// 归并排序入口
public static void mergeSort(int[] a, int first, int last, int[] temp){
    if(first >= last){
        return;
    }
    
    int mid = (first + last) / 2;
    mergeSort(a, first, mid, temp);
    mergeSort(a, mid + 1, last, temp);
    mergeArray(a, first, mid, last, temp);
}

// 合并两个有序数组
public static void mergeArray(int[] a, int first, int mid, int last, int[] temp){
    int i = first, j = mid + 1, k = 0;
    while(i <= mid && j <= last){
        if(a[i] < a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    while(i <= mid){
        temp[k++] = a[i++];
    }
    while(j <= last){
        temp[k++] = a[j++];
    }

    /*for(i = 0; i < k; i++){
        a[first + i] = temp[i];
    }*/
    System.arraycopy(temp, 0, a, first, k);
}

代码中有一些地方,需要注意一下,例如递归,临时数组的运用,还有排序后记得把临时数组的序列写回源数组。

Be the First to comment.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

66 views