归并排序

自顶向下的归并排序

java描述

public class Merge {
    
    // 归并的辅助函数
    private static Comparable[] axu;
        
    
    // 实现了Comparable接口的都可以比较
    public static void sort(Comparable[] a){
        axu = new Comparable[a.length];
        sort(a, 0, a.length - 1);
        
    }
    
    private static void sort(Comparable[] a, int start, int end){
        
        if(start >= end){
            return;
        }
        
        int mid = start + (end - start) / 2;
        // 将左边排序
        sort(a, start, mid);
        // 将右边排序
        sort(a, mid + 1, end);
        // 归并
        merge(a, start, mid, end);
    }
    
    // 归并排序 将两个分别有序的数组合并成一个数组
    public static void merge(Comparable[] a, int start, int mid, int end){
        // 左边
        int i = start;
        int j = mid + 1;
        
        // 将a[start...end] 复制到axu[start...end]中
        for(int k = start; k <= end; k++){
            axu[k] = a[k];
        }
        
        for(int k = start; k <= end; k++){
            if(i > mid){
                a[k] = axu[j];
                j++;
            }else if(j > end){
                a[k] = axu[i];
                i++;
            }else if(less(axu[i], axu[j])){
                a[k] = axu[i];
                i++;
            }else{
                a[k] = axu[j];
                j++;
            }
        }
    }
    
    
    
    public static void main(String[] args) {
        Integer[] a = {2, 3, 1, 3, 4, 8, 6, 10};
        sort(a);
        assert isSorted(a);
        show(a);
    }
    
    public static boolean less(Comparable V , Comparable W){
        return V.compareTo(W) < 0;
    }
    
    public static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ");   
        }
        System.out.println();
    }
    
    // 测试数组元素是否有序
    public static boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i-1])){
                return false;
            }
        }
        return true;
    }
}