当前位置:首页 » 《随便一记》 » 正文

归并排序(Java)

15 人参与  2024年02月12日 10:31  分类 : 《随便一记》  评论

点击全文阅读


        归并排序是常见的八大排序算法之一,归并排序也是一种时间复杂度比较好的一种算法,为0(n*logn)级别。

        归并排序可以用递归和非递归两种方式来实现,当然,递归方法是比较简单的,而非递归则是相对而言比较难的一种思路。

        归并排序的总体思路就是将一个大的无序数组,划分为多个内部有序的数组,而组间可能是无序的,通过合并相邻两组得到一个新的有序数组来实现,最终合并成总体的大数组,即完成排序。

        因此,对于归并排序,我们需要先向下分组,然后再将各个数组合并,得到一个新的数组,直到最后合并成一个数组,算法结束。

        具体细节,则是通过将大数组划分,首先划分为每一组单个元素,单个元素的数组可以认为是有序的。如何依次从左向右,每次取两个相邻数组,进行合并,即两个有序数组的合并,合并完以后,再找下一组两个相邻的数组进行合并(并不包括上次合并好的数组),直到最后只有一个组或者没有组了,就重新从头开始合并,继续上述步骤。

        对于递归写法,我们可以认为数组中的各个元素都是二叉树的叶子结点,依据上述思路,两两合并成一个结点,最后合并成一个结点,即排序结束。

        对于非递归写法,我们可以设置一个变量来存储要比较的数组长度,从一开始,到数组长度结束,即使分开后的数组元素个数并不等于这个变量,只要有和他配对的就可以合并。

        代码测试通过力扣中的题目进行测验。

代码实现:

递归:

class Solution {    public int[] sortArray(int[] nums) {        mergeSort(nums,0,nums.length-1);        return nums;    }    public void mergeSort(int[] nums,int left,int right){        if(right==left){            return;        }        int center=(left+right)/2;        mergeSort(nums,left,center);        mergeSort(nums,center+1,right);        merge(nums,left,center,right);    }    public void merge(int[] nums,int left,int center,int right){        int i=left;        int j=center+1;        int[] temp=new int[right-left+1];        int count=0;        while(i<=center && j<=right){            temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++];        }        while(i<=center){            temp[count++]=nums[i++];        }        while(j<=right){            temp[count++]=nums[j++];        }        for(int k=0;k<temp.length;k++){            nums[left+k]=temp[k];        }    }}

        力扣提交结果:

非递归:

class Solution {    public int[] sortArray(int[] nums) {        for(int l,m,r,step=1;step<nums.length;step*=2){            l=0;//设置初始值            while(l<nums.length){//有左边的组                m=l+step-1;                if(m+1>=nums.length){//如果没有右边的组,就退出                    break;                }                r=Math.min(l+(step*2)-1,nums.length-1);//获取右边界,取两者的最小值                merge(nums,l,m,r);//将两个组合并                l=r+1;//找到下一个左边的组            }        }        return nums;    }    public void merge(int[] nums,int left,int center,int right){        int i=left;        int j=center+1;        int[] temp=new int[right-left+1];        int count=0;        while(i<=center && j<=right){            temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++];        }        while(i<=center){            temp[count++]=nums[i++];        }        while(j<=right){            temp[count++]=nums[j++];        }        for(int k=0;k<temp.length;k++){            nums[left+k]=temp[k];        }    }}

力扣提交结果:


点击全文阅读


本文链接:http://zhangshiyu.com/post/68218.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1