欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构和算法14 之归并排序

程序员文章站 2022-11-10 22:01:12
归并算法的中心是归并两个已经有序的数组。归并两个有序数组a和b,就生成了第三个数组c,数组c包含数组a和b的所有数据项,并且使它们有序的排列在数组c中。首先我们来看看归并的过程,然后看它是如何在排序...

归并算法的中心是归并两个已经有序的数组。归并两个有序数组a和b,就生成了第三个数组c,数组c包含数组a和b的所有数据项,并且使它们有序的排列在数组c中。首先我们来看看归并的过程,然后看它是如何在排序中使用的。

假设有两个有序数组,不要求有相同的大小。设数组a有4个数据项,数组b有6个数据项,它们要被归并到数组c中,开始时数组c有10个存储空间,归并过程如下图所示:

数据结构和算法14 之归并排序

归并排序的思想是把一个数组分成两半,排序每一半。然后用merge方法将数组的两半归并成一个有序的数组。被分的每一半使用递归,再次划分排序,直到得到的子数组只含有一个数据项为止。正如上面所说的,归并排序需要额外的一个和ab两个数组总和相等的空间,如果初始数组几乎沾满了整个存储器,那么归并排序就不能工作了。

归并排序的思想很简单,下面我们来看看具体实现:

 

public void mergesort(int[] source) {
    int[] workspace = new int[source.length];
    recmergesort(source,workspace, 0, source.length-1);
}

private void recmergesort(int[] source, int[] workspace, int lowerbound, int upperbound) {
    if(lowerbound == upperbound) {
        return;
    }
    else {
        int mid = (lowerbound + upperbound) / 2;
        recmergesort(source, workspace, lowerbound, mid); //左边排
        recmergesort(source, workspace, mid+1, upperbound); //右边排
        merge(source, workspace, lowerbound, mid+1, upperbound);//归并
    }
}

private void merge(int[] a, int[] workspace, int lowptr, int highptr, int upperbound) {
    int j = 0;
    int lowerbound = lowptr;
    int mid = highptr - 1;
    int n = upperbound - lowerbound + 1;
    while(lowptr <= mid && highptr <= upperbound) {
        if(a[lowptr] < a[highptr]) {
            workspace[j++] = a[lowptr++];
        }
        else {
            workspace[j++] = a[highptr++];
        }
    }
    while(lowptr <= mid) {
        workspace[j++] = a[lowptr++];
    }
    
    while(highptr <= upperbound) {
        workspace[j++] = a[highptr++];
    }
    
    for(j = 0; j < n; j++) {
        a[lowerbound + j] = workspace[j];
    }
}

 

算法分析:归并排序的运行时间最差、最好和平均都是o(nlogn),但是它需要额外的存储空间,这在某些内存紧张的机器上会受到限制。归并算法是由分割和归并两部分组成的,对于分各部分,如果我们使用二分查找,时间是o(nlogn),在最后归并的时候时间是o(n),所以总时间是o(nlogn)。空间复杂度为o(n)。

归并排序就写这么多,如有错误之处,欢迎留言指正~

_____________________________________________________________________________________________________________________________________________________