アルゴリズム読書ノート-ソートアルゴリズム-集計ソート

まとめ
集計ソートは主に分治の考え方を用い,配列を小さいセグメントに分割し,小さなセグメントをソートして小さなセグメントを統合することでソートを完了する.集計ソートの時間的複雑さはO(nlgn)であり,nlgnが比較に基づくすべてのアルゴリズム効率の上限であることを実証できた.
本を読んでいるうちに、自分のコードスタイルが幼稚すぎることに気づいた.例えば、私はa[i]=aru[j];j++;アルゴリズムの本の上でただ1つのa[i]=a[j+];できました.原因は自分でこの方面で考えていないのかもしれなくて、いつも机能を书いておけばいいと思って、これらの用法に対して深い理解がありません.例えばforループでは、1つ目は変数を宣言するために使用され、2つ目はブール式であり、2つ目は境界を除いた判断を行うことができ、3つ目は各ループが完了した後の操作であり、これらの特性を利用して自分のコードをより簡潔にすることができる.
merge集計配列の関数

     /*
     *          ，       、       
     */
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        int i = lo,j = mid+1;
        
        for(int k=lo;k<=hi;k++) aux[k] = a[k];//        
        
        for(int k=lo;k<=hi;k++){
            if(less(aux[j],aux[i])) a[k]=aux[j++];
            else if (i>mid) a[k]=aux[j++];
            else if(j>hi) a[k]=aux[i++];
            else a[k]=aux[i++];
        }

上から下への集計ソート
主な思想:再帰的な方法を利用して分解して、合併します

    /*
     *          
     *     ：   ，              
     */
    public static void mergeSort(Comparable[] a){
        aux = new Comparable[a.length];
        int lo = 0,hi = a.length;
        mergeSort(a, lo, hi);
    }
    /*
     *   、    
     */
    public static void mergeSort(Comparable[] a,int lo,int hi){
        if(hi<=lo) return;
        int mid =lo + (hi-lo)/2-1;
        mergeSort(a, lo, mid);
        mergeSort(a, mid, hi);
        merge(a,lo,mid,hi);
    }

下から上への集計ソート
主な考え方:まず配列を分解してから集計する

    /*
     *          
     *     ：   ，           
     */
    public static void bottomMergeSort(Comparable[] a){
        int N = a.length;
        aux = new Comparable[a.length];
        for(int sz = 1;sz