java实现数组的数字 归并排序(O(NlogN))

实现过程：
从中点分开 先让数组的左侧排好序 再让右侧排好序 然后整体整合,左右各一个指针，如果P1小于P2指针指向的数，就把P1指的数存入一个新的数组,P1向右移动一个单位，继续和P2比较然后直到比较到左边或者右边的数组越界， 把另外一个数组剩下的加进即可

时间复杂度O(NlogN）
比选择排序冒泡排序好的原因是没有浪费比较的次数

import java.util.Scanner;

public class code09 {
    

    //进行归并排序 递归方法
    public static void process(int[] arr,int L,int R){
        if(L==R){
            return;
        }
        //求中点
        int mid=L+((R-L)>>1);
        //将左边的一半排好序
        process(arr,L,mid);
        //将右边的一半【排好序
        process(arr,mid+1,R);
        //合并左边和右边
        merge(arr,L,mid,R);
    }
    //合并方法
    public static void merge(int[] arr,int L,int M,int R){
        //新建一个辅助数组
        int[] help=new int[R-L+1];
        int i=0;
        //定义右边的指针
        int p1=L;
        //指向右边的数组
        int p2=M+1;
        //当数组没有越界的时候
        while (p1<=M&&p2<=R){
            //当左边的指针里面的数小于右边的数时就将选择那个小的 然后指针加加
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //当左边越界
        while (p1<=M){
            help[i++]=arr[p1++];
        }
        //当右边越界
        while (p2<=R){
            help[i++]=arr[p2++];
        }
        //再将辅助数组中的数赋值给原数组
        for (i=0;i测试结果如下
 
 
新创建一个公众号 Rockey小何同学 想相互交流的同学可以关注一下哈！ 感谢支持！					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5719890.html