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

3837 ワード

アルゴリズム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
    好きならいいね、ありがとう!