Skip to main content
 首页 » 编程设计

java算法之归并排序(递归方式)

2022年07月18日29jackei
/** 
 * @desc: 归并排序 
 * @author: 毛会懂 
 * @create: 2020-12-24 11:17:00 
 **/ 
public class Merge { 
 
    public static void sort(Comparable[] arr){ 
        int low = 0; 
        int high = arr.length - 1; 
        sort(arr,low,high); 
    } 
 
    public static void sort(Comparable[] arr,int low,int high){ 
        if(low >= high){ 
            return; 
        } 
        int middle = low + (high - low) / 2; 
 
        sort(arr,low,middle); 
        sort(arr,middle + 1,high); 
        merge(arr,low,middle,high); 
    } 
 
    public static void merge(Comparable[] arr,int low,int middle,int high){ 
        //这种方式每次递归都要创建一个temp数组,也不太友好 
        Comparable[] temp = new Comparable[high -low +1]; 
 
        //定义指向temp的下标位置 
        int k = 0; 
        //定义指向arr[low] -- arr[middle]的下标位置 
        int i = low; 
        //定义指向arr[middle + 1] -- arr[high]的下标位置 
        int j = middle + 1; 
        while (i <= middle && j <= high){ 
            if(isExchange(arr[i],arr[j])){ 
                temp[k++] = arr[j++]; 
            }else{ 
                temp[k++] = arr[i++]; 
            } 
        } 
 
        while (i <= middle){ 
            temp[k++] = arr[i++]; 
        } 
 
        while (j <= high){ 
            temp[k++] = arr[j++]; 
        } 
 
        //最后把temp数组赋值到arr数组中 
        for(int index = low; index <=high;index++){ 
            arr[index] = temp[index - low]; 
        } 
    } 
 
    private static Boolean isExchange(Comparable o1,Comparable o2){ 
        return o1.compareTo(o2) > 0; 
    } 
} 
 
    //归并排序 
    public static void main(String[] args) { 
//        Integer[] arr = {10,8,20,30,5,7,4,12,40,30,1,2,4,3,100,5,32,45,23,66,45,7,55,79,6}; 
//        Merge.sort(arr); 
//        Arrays.asList(arr).forEach(System.out::println); 
 
        Person[] persions = {new Person("b", 11), new Person("a", 10), new Person("c", 12), new Person("b", 111), 
                new Person("a", 5), new Person("c", 4)}; 
        Merge.sort(persions); 
        for (Person person : persions) { 
            System.out.println(person); 
        } 
    } 

  


本文参考链接:https://www.cnblogs.com/maohuidong/p/14184520.html