五分钟教你学会归并排序

举报
Tom forever 发表于 2019/10/26 10:49:25 2019/10/26
【摘要】 今天来讨论下归并排序。只要五分钟便能掌握归并排序的原理。归并算法的中心是归并两个已经有序的数组。归并两个有序数组 A 和 B,就生成了第三个数组 C,数组 C 包含数组 A 和 B 的所有数据项,并且使它们有序的排列在数组 C 中。首先我们来看看归并的过程,然后看它是如何在排序中使用的。假设有两个有序数组,不要求有相同的大小。设数组 A 有 4 个数据项,数组 B 有 6 个数据项,它们要被...

今天来讨论下归并排序。只要五分钟便能掌握归并排序的原理。

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

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

640?tp=webp&wxfrom=5&wx_lazy=1&wx_co=1



归并排序的思想是把一个数组分成两半,排序每一半。然后用 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)。

归并排序是稳定的,由于没有发生数据交换,所有当 a=b 的时候,a 一开始如果在 b 前面,则其每一次合并后仍然在 b 前面,故该排序算法是稳定的。



转载声明:本文转载自公众号【程序员私房菜】。    

原文链接:https://mp.weixin.qq.com/s/YBlJYMHVEQamdlWVrs42nw


【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200