归并排序原理（java实现）

旧城等待， 2022-06-10 07:52 138阅读 0赞

归并排序也是排序算法的一种，它是将两个已经排好序的数组，合并成另一个排好序的数组，原理是这样的：定义一个新数组，再定义两个指针，分别指向两个已经排好序的数组的第一个元素，然后两者进行比较，较小的那个数放到新定义的那个数组的第一个位置，同时，将较小的那个数的下标加1，再跟刚刚比他大的那个数比较，两者中较小的数就放到新数组里面，最后比较完之后，若其中一个数组有剩余的元素没有比较，就将剩余的元素直接插入到新数组中。  
　　  
　　听起来有些绕，还是举个例子，比如现在有两个排好序的数组arr1 = \{1,3,5,8,12,45,89\}和arr2 = \{2,4,6,7,9,10,11\}，再定义一个新数组arr 长度是arr1.length+arr2.length用来存放合并之后的数组，定义两个指针i和j，分别指向arr1中的第一个元素和arr2中的第一个元素，1和2,1比2小，那么就把1放到arr中的第一个位置，这时候arr变为\[1\]，之后，挪动i，使i指向3，再去跟j对应的元素比较，2小于3，所以把2放入到arr中去，arr就变成了\[1,2\]，再挪动j，让j加1，指向4，再去比较……最后，就实现了两个有序数组合并成一个有序数组，怎么样？是不是很简单？  
　　  
　　下面是Java代码实现

class Demo
    {
        public static void main(String[] args)
        {
            //定义两个整型数组
            int[] arr1 = {
       1,3,5,8,12,45,89};
            int[] arr2 = {
       2,4,6,7,9,10,11};
            //调用归并排序函数，赋值给新数组temp
            int[] temp = mergerSort(arr1,arr2);
            //输出排序后的数组
            for(int i=0;i<temp.length;i++)
            {
                System.out.print(temp[i]+" ");
            }
        }
        //定义归并排序算法
        public static int[] mergerSort(int[] a1,int[] a2)
        {
            //left控制a1数组的下标
            int left = 0;
            //right控制a2数组的下标
            int right = 0;
            //x控制新数组的下标
            int x = 0;
            //定义一个新数组arr
            int[] arr = new int[a1.length+a2.length];
            while(left<a1.length && right<a2.length)
            {
                //如果left指向的数小于right指向的数
                //就把arr[left]写入到新数组arr中
                if(a1[left]<a2[right])
                {
                    arr[x++] = a1[left++];
                }
                //如果right指向的数小于left指向的数
                //就把arr[right]写入到新数组arr中
                else
                {
                    arr[x++] = a2[right++];
                }
            }
            //比较完后，若a1数组有剩余，将剩余部分写入新数组的后面
            while(left<a1.length)
            {
                arr[x++] = a1[left++];
            }
            //比较完后，若a2数组有剩余，将剩余部分写入新数组的后面
            while(right<a2.length)
            {
                arr[x++] = a2[right++];
            }
            //返回数组
            return arr;
        }
    }

看到这里，大家可能会说，这个是两个数组合并成一个数组，而且还是两个有序的数组合并成一个有序的数组，那我要是想把一个数组用归并排序来排一下序就不行了吗？怎么可能不行，那还要归并排序有什么用……  
　　  
　　一个数组的归并排序算法，其实跟上面说的这个道理是一样的，上面是两个有序的数组合并成一个有序的数组，你是不是也可以把一个无序的数组拆分成多个有序的数组呢？这是什么意思？意思就是说，一个无序的数组，你把它每个元素都看成一个只有一个元素数组，那么这个数组是不是有序的，之后，两个相邻数组之间（其实就是两个相邻的数），是不是就可以用我们上面说的归并排序算法了，排序完之后就又变成了好几个有序的数组，然后相邻的数组之间再用归并排序，是不是有变得有序了，知道最后所有的数组都合并，那整个数组的排序就ok了。读者们可能也看出来了，这个得用递归实现，首先是拆，将一个数组拆成一个一个的元素，再把他们一个一个的归并，这就是原理。  
　　  
　　举个例子，一个数组中四个数\{4,1,2,3\}，先把他们拆成一个一个的，也就是\{4\},\{1\},\{2\},\{3\}，之后，两两归并，就变成了\{1,4\},\{2,3\}，再两两归并，就变成了\{1,2,3,4\}，懂了吗？看起来很简单，实际上在递归的时候需要很强的理解才行，记住，一个数组的归并排序，分两步，第一，拆分，第二，合并  
　　  
　　下面是Java代码实现

class Demo
    {
        public static void main(String[] args)  
        {
            //定义一个无序数组
            int[] arr = {
       3,1,2,4,5,7,6,8};
            //left在这里定义，控制左半部分的首元素
            int left = 0;
            //right指向最后一个元素
            int right = arr.length-1;
            //调用排序函数
            sort(arr,left,right);
            //输出排序后的数组
            for(int i=0;i<arr.length;i++)
            {
                System.out.println(arr[i]);
            }
        }
        public static int[] sort(int[] arr,int left,int right)
        {
            //mid其实是作为分割的指针
            int mid = (left+right)/2;
            //递归拆分，调用归并（这里是关键，需要读者好好思考）
            //读者可以用元素少一点的数组先思考明白了，再去想递归是什么回事
            if(left<right)
            {
                sort(arr,left,mid);
                sort(arr,mid+1,right);
                merger(arr,left,right,mid);
            }
            return arr;
        }
        //归并函数
        public static void merger(int[] arr,int left,int right,int mid)
        {
            //定义一个新数组来存放排序后的数
            int[] temp = new int[right-left+1];
            //x控制新数组的下表
            int x = 0;
            //j指向右半部分数组的首元素
            int j = mid+1;
            //将left赋值给l，最后覆盖的时候要用到，否则left值被改变
            int l = left;
            while(left<=mid && j<=right)
            {
                if(arr[left]<arr[j])
                {
                    temp[x++] = arr[left++];
                }
                else
                {
                    temp[x++] = arr[j++];
                }
            }
            //处理剩余数组
            while(left<=mid)
            {
                temp[x++] = arr[left++];
            }
            //处理剩余数组
            while(j<=right)
            {
                temp[x++] = arr[j++];
            }
            //覆盖原来的数组
            for(int i=0;i<temp.length;i++)
            {
                arr[i+l] = temp[i];//
            }
        }
    }

递归过程不是很好理解，需要读者慢慢去掌握，不要心急