Androidアルゴリズム01-蛮力法

2238 ワード

アルゴリズム01-蛮力法
一、蛮力法の紹介
蛮力法(brute force method、貧乏挙法または列挙法とも呼ばれる)は簡単に直接問題を解決する方法であり、問題の記述に直接基づいていることが多いため、蛮力法も最も応用しやすい方法である.しかし,蛮力法で設計されたアルゴリズムの時間特性も往々にして最も低く,典型的な指数時間アルゴリズムは一般に蛮力探索によって得られる.
一般的な蛮力法:泡のソート、ソートの選択.
二、泡の順序付け
1、基本思想
バブルソート(Bubble Sort)は、コンピュータ科学分野の簡単なソートアルゴリズムである.このアルゴリズムの名前の由来は,大きな要素が交換を介して徐々に数列の先端に「浮かぶ」ため,「泡ソート」と呼ばれているからである.
ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.
バブルソートは安定したソートアルゴリズムであり、少量のデータのソート(10枚以内)に適しており、例えば金花を揚げる.
2、コード実現
public static > void bubbleSort(E[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }

    //      
    for (int i = 0; i < arr.length - 1; i++) {
        //        :               
        boolean flag = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            E temp = arr[j];
            if (arr[j].compareTo(arr[j + 1]) > 0) {
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
            }
        }
        if (flag) {
            return;
        }
    }
}

三、ソートの選択
1、基本思想
選択ソート(Selection sort)は単純で直感的なソートアルゴリズムである.その動作原理は、並べ替えられるデータ要素の中から最小(または最大)の要素を選択するたびに、並べ替えられるデータ要素がすべて並ぶまでシーケンスの開始位置に格納することです.
選択ソートは不安定なソート方法である(例えばシーケンス[5,8,3]は初めて[5]と[3]を交換し、5を8の後ろに移動させる).選択ソートの移動回数は少なく、少量のデータのソート(10~20)に適している.
2、コード実現
public static > void selectSort(E[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }

    for (int i = 0; i < arr.length - 1; i++) {
        //     
        int index = i;
        for (int j = i + 1; j < arr.length; j++) {
            E temp = arr[index];
            if (temp.compareTo(arr[j]) > 0) {
                index = j;
            }
        }

        //       
        if (index != i) {
            E temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

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