Androidアルゴリズム05-減算法

アルゴリズム05-減算法
一、紹介
減治法は,一歩一歩一定の問題規模(−1,−k,−n/2など)を縮小し,最後に最小の小さな問題となる.
減治法の一般的な応用:スタックソート、深さ優先検索.
二、スタックの順序付け
1、基本思想
ヒープソート:完全なツリーの昇順ソートに基づいています.
ヒープのソート手順:

線形構造(配列など)を完全二叉木として並べ替える:配列中の1つの要素Aの下にkとマークされている場合、下に(k-1)/2とマークされている要素はAの親ノードに相当し、下に2 k+1とマークされている要素はAの左サブノードに相当し、下に2 k+2とマークされている要素はAの右サブノードに相当する.

n個の要素を並べ替え、最小値を配列の先頭に置く:まずノードkの左サブツリーの最小値をkの左サブノードに置き、次にノードkの右サブツリーの最小値をkの右サブノードに置き、次にノードkとその左右サブノードの最小値が配列の最小値である.ここでは再帰が必要です.

配列の最小値を取り出し、配列Mを入れる.

はn=n-1とし、n=0になるまでステップ2、3を繰り返し、ソートが完了する:Mは拍好順の配列である.

≪適用|Apply|emdw≫:データ・ソースが無秩序またはチェーン構造の場合、二分検索を行います.一般的にソートには使用されず、スペースの複雑さが高すぎます.
2、コード実現

public static > E[] heapSort(E[] arr) {
    if (Tool.isEmpty(arr)) {
        return null;
    }

    //    new      ，    Arrays.copyOf()
    E[] result = Arrays.copyOf(arr, arr.length);
    //      ：  -1
    for (int i = 0; i < arr.length; i++) {
        //         
        int n = arr.length - i;
        //      ：          ，        
        heapSort(arr, n, 0);
        //      
        result[i] = arr[0];
        //            
        arr[0] = arr[n - 1];
    }

    return result;
}

/**
 *      ：                  
 * @param arr：      
 * @param n：      ，      
 * @param k：        
 */
public static > void heapSort(E[] arr, int n, int k) {
    //      
    int left = 2 * k + 1;
    //      
    int right = 2 * k + 2;
    if (left >= n) {
        return;
    }

    //              
    heapSort(arr, n, left);
    //               
    heapSort(arr, n, right);

    E data = arr[k];
    E l = arr[left];
    //        ，       MAX
    E r = right < n ? arr[right] : null;
    //          ，    
    if (data.compareTo(l) <= 0 && (r == null || data.compareTo(r) <= 0)) {
        return;
    }
    //         ，            
    if (r == null || l.compareTo(r) < 0) {
        arr[left] = data;
        arr[k] = l;
        //         ，            
    } else {
        arr[right] = data;
        arr[k] = r;
    }
}

三、深さ優先検索
1、基本思想
深さ優先検索は深さ優先で検索する思想で、一つの方向に沿ってまっすぐ行って、道がなくなったら戻って、それから方向を変えて探して、ゴールを見つけることを知っています.
操作手順:

は2次元配列で迷路をシミュレートし、配列の値:0は通じる、1は通じない、2は通る、3は壁を表す.始点と終点を指定します.

始点から左下右上の順に検索し、次の点まで行ける場合はその値を2とマークし、この点を新しい始点として左下右上の順に検索します.次のポイントに移動できない場合は、その値を1としてマークし、前のポイントに戻り、残りの方向から検索します.

手順2を繰り返し、ゴールまで歩いたことを知っています.

応用:迷宮で道を探す
2、コード実現

/**
 * @param arr           。  0     ，1     ，2    ，3   。
 * @param startX      
 * @param startY      
 * @param endX        
 * @param endY        
 */
public static boolean dfsSort(int[][] arr, int startX, int startY, int endX, int endY) {
    if (startX < 0 || startY < 0 || endX < 0 || endY < 0) {
        return false;
    }
    //     
    if (arr[endX][endY] == 2) {
        return true;
    }

    //      ，           
    if (arr[startX][startY] == 0) {
        //     
        arr[startX][startY] = 2;
        //      
        if (dfsSort(arr, startX - 1, startY, endX, endY)) {
            return true;
            //      
        } else if (dfsSort(arr, startX, startY - 1, endX, endY)) {
            return true;
            //      
        } else if (dfsSort(arr, startX + 1, startY, endX, endY)) {
            return true;
            //      
        } else if (dfsSort(arr, startX, startY + 1, endX, endY)) {
            return true;
            //     ，    1，    
        } else {
            arr[startX][startY] = 1;
            return false;
        }
    }
    return false;
}

最後に
コードアドレス:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/arithmetic/ReduceConquer.java
データ構造とアルゴリズムのテーマ:https://www.jianshu.com/nb/25128590
好きならいいね、ありがとう!