【算法学习】归并排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法学习】归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含829字，纯文字阅读大概需要2分钟。

内容图文

1.算法思路：

　　（1）将待排序数组分为两份，利用递归将两份数组排好序

　　（2）将两个有序数组归并成一个有序数组。

　　　　　　实现方法：

　　　　　　　　a.设置两个指针，分别指向两个数组的开头，比较指针所指向的数字，将较小的数字加入一个辅助数组中，指针前移，直到其中一个指针溢出

　　　　　　　　b.将未溢出的数组剩余的元素加入辅助数组中

　　　　　　　　c.将辅助数组整体拷贝到原来的数组中

2.代码（JAVA）:

public class mergesort{
    public static void mergeSort(int[] arr, int l, int r) {
        if(l<r){
            int mid=l+(r-l)/2;
            mergeSort(arr,l,mid);
            mergeSort(arr,mid+1,r);
            merge(arr,l,r);
        }
    }
    
    public void merge(int[] arr,int l,int r){
        int[] tmp=new int[r-l+1];
        int mid=l+(r-l)/2;int p1=l;
        int p2=mid+1;
        int i=0;
        while(p1<=m&&p2<=r){
            if(arr[p1]<arr[p2])
                tmp[i++]=arr[p1++];
            else
                tmp[i++]=arr[p2++];
        }
        while(p1<=m)
            tmp[i++]=arr[p1];
        while(p2<=r)
            tmp[i++]=arr[p2];
        for(i=0;i<arr.length;i++){
            arr[l+i]=tmp[i];
        }
    }
}

 

3.算法分析：

　　时间复杂度：O（N*logN）

 

　　

内容总结

以上是互联网集市为您收集整理的【算法学习】归并排序全部内容，希望文章能够帮你解决【算法学习】归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---