Javaソートアルゴリズムの詳細と例の要約-超詳細

55895 ワード
Java
バブルソート、選択ソート、直接挿入ソート、二分法ソート、ヒルソート、高速ソート、スタックソート、集計ソート、基数ソートの9つのソートアルゴリズムの詳細とコード例.
例の中ですべて小さいから大きいまで並べ替えて、符号化の方式は本人の理解の構想で、アルゴリズムの思想も自分の理解の口語の表現の方式で、もっと正確なアルゴリズムの思想とコードの例を見たいならば直接各アルゴリズムの百科を検索することができます
サンプルソースアドレス
一、泡立ちソート
1、アルゴリズム思想
両者を比較する、後者が前者より大きい場合は交換位置とする.
1周あたりの最大数が最後になると、本輪比較の最大値が最後の不動に置かれることが決定する.
をすべて巡回するまで1、2を循環する.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ：    ，      ，                ，         
 */
private void bubbleSort() {

    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    
}

時間複雑度O(n²)
二、ソートの選択
1、アルゴリズム思想
すべての数の最大値の下付きを見つけます.
最大値の下付き文字と最後の位置の数値交換位置を見つけ、毎回見つけた最大値は最後のに固定される.
すべてのが見つかるまで、1、2の操作をループします.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ：           ，                 ，             
 */
private void selectSort() {

    for (int i = 0; i < array.length; i++) {

        //          ，   0
        int max = 0;
        for (int j = 0; j < array.length - i; j++) {

            //              
            if (array[max] < array[j]) {
                max = j;
            }
        }

        //                   
        int temp = array[array.length - i - 1];
        array[array.length - i - 1] = array[max];
        array[max] = temp;
    }

}

時間複雑度O(n²),しかし、選択ソートは1ラウンド当たり1回のみ交換ため、実際の性能は発泡よりも優れている.
三、直接挿入ソート
1、アルゴリズム思想
位置1の数値nから、先に遍歴する数値集合を配列mと見なすと、nをmに挿入する.
nが集合mに挿入するときは後から前へ比較し、nより大きい場合は1ビット後ろへ移動する、nより小さい場合は現在位置がnを挿入する位置である.
1,2の操作により、nを挿入する毎にmの集合が整列するシーケンスであることが保証される.
ループ1、2、3の操作は、セット内のすべての数値を1回挿入する、すなわちソート完了である.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *       ： 1      ，                  
 *                   ，       
 */
private void insertSort() {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];
        int j;
        //                      
        for (j = i - 1; j >= 0; j--) {
            if (temp < array[j]) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = temp;
    }
}

時間複雑度O(n²)
四、二分法並べ替え
二分法ソートは直接挿入ソートの改良バージョンであり、直接挿入ソートを前方集合に挿入する際に採用する方式は逐次比較であり、二分法は二分比較を採用する.
1、アルゴリズム思想
位置1の数値がnであり、先に遍歴する数値集合を配列mとすると、nをmに挿入する.
nを集合mに挿入する場合は二分法を用いる、まずmの中間の値を比較し、nより大きい場合は、分割された集合の左半分または右半分に値がないまで後半分の集合の中間の値を比較し続けると、現在の中間値の位置はnがmに挿入する位置となる.
1,2の操作により、nを挿入する毎にmの集合が整列するシーケンスであることが保証される.
ループ1、2、3の操作は、セット内のすべての数値を1回挿入する、すなわちソート完了である.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *       ： 1    ，          left，  right，              
 *          right              ，     left
 *     left>right   
 */
private void binaryInsertSort() {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];
        int left = 0, right = i - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (temp < array[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        //                  
        for (int j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = temp;
    }
}

時間複雑度O(nlogn)五、ヒルソート
1、アルゴリズム思想
増分mを定義し、集合の長さがnである場合、集合をn/mグループに分割し、各グループの内部で比較ソートを行う.
各グループ内で比較する方法は要求なく、挿入または二分法ででもよい.
1つの集合を{4,1,2,3}と並べ替え、mを2と定義すると、4と2の比、1と3の比の2つのグループに分割されます.
従って、1、2の考え方で比較する毎にm群内の数値をに並べ替えることができる.
mの値を絶えず変化させ、複数回のパケットを巡回するとに並べ替えることができる.
2、コード例
mの変化の仕方は様々であるが、異なる変化の仕方で並べ替え結果や効率が異なる場合がある.ここでは、m=m/2 を例示する.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ：      m，          n，      n/m ，        
 *   m  ，                
 */
private void shellSort() {
    int m = array.length;
    while (true) {
        //            m/2
        m = m / 2;
        //          n/m  
        for (int i = 0; i < m; i++) {
            //                 i  
            for (int j = i + m; j < array.length; j += m) {
                //           （            ，         ）
                int temp = array[j];
                int k;
                //                      
                for (k = j - m; k >= i; k -=m) {
                    if (temp < array[k]) {
                        array[k + m] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + m] = temp;
            }
        }

        if (m == 1) {
            break;
        }
    }
}

時間複雑度O(nlogn)六、クイックソート
1、アルゴリズム思想
高速ソートの考え方は、主に基準点mを設定することであり、ここでは、設定するたびに基準点が各グループの最初の数値であると仮定する.
基準点mを持って集合の中で比較し、置くべき位置を見つける.
比較方式は主に集合の中で一番左の下付きラベルleft、一番右の下付きラベルrightを定義し、左から比較し、mより小さいとleft++となり、mより大きいと停止し、leftの下付きラベルの値をrightの下付きラベルの値に賦値し、その後同じようにrightを比較し、mより大きいとright–を比較し、mより小さいとleftの下付きラベルの値に賦値する.left=rightの後、比較はを完了する
ステップ3の比較の後、m点の並べ替えがある位置を見つけることができ、その後、集合は前後の半分に分けられ、それぞれ1、2、3のように並べ替えられ、すべての分割比較が完了すると並べ替えが完了するに戻る.
手順3の考え方が複雑であるため、ここでは「アハ!アルゴリズム」という本のイラストを引用してデモを行い、図の中で最初の点6を基準点とし、6ソート後の位置を見つけた.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ：                 
 */
private void quickSort() {
    quickSort(0, array.length - 1);
}

/**
 *                    ，           
 *                   ，         ，             
 *
 * @param low        
 * @param high       
 */
private void quickSort(int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = getMiddle(low, high);
    quickSort(low, mid - 1);
    quickSort(mid + 1, high);
}

/**
 *                   
 *
 * @param low        
 * @param high      
 * @return          
 */
private int getMiddle(int low, int high) {
    int temp = array[low];
    while (low < high) {
        while (low < high && array[high] >= temp) {
            high--;
        }
        array[low] = array[high];

        while (low < high && array[low] <= temp) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = temp;
    return low;
}

時間複雑度O(nlogn)七、スタックの順序付け
1、アルゴリズム思想
配列は、すべてのノードの親ノードの値がリーフノードの完全なツリーよりも大きいツリーのように構築される.
リーフノードが親ノードよりも大きい場合、交換位置ルートノードが最大値である、ルートノードを最後のリーフノードと交換位置とする.
1、2の操作を繰り返し、毎回最大値を探すと最後に並べ替えてを完了します.
スタックソートは完全なツリーのデータ構造に応用されているため、理解しにくいため、ネット上でアルゴリズムのデモを探した画像はを参照してください.
2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *    ，           ，              
 *                         ，             
 */
private void heapSort() {

    //           ，        
    buildMaxHeap();

    for (int i = array.length - 1; i > 0; i--) {
        //                
        exchangeValue(0, i);

        //          ， 0                
        maxHeap(i, 0);
    }

}


/**
 *        ，          ，               
 */
private void buildMaxHeap() {
    int length = array.length;
    for (int i = length / 2 - 1; i >= 0; i--) {
        maxHeap(length, i);
    }
}


/**
 *           ，      ，          
 *
 * @param length         
 * @param node          
 */
private void maxHeap(int length, int node) {
    int left = 2 * node + 1;
    int right = 2 * node + 2;
    //                     
    int maxIndex = node;
    if (left < length && array[left] > array[maxIndex]) {
        maxIndex = left;
    }
    if (right < length && array[right] > array[maxIndex]) {
        maxIndex = right;
    }

    //          ，           
    if (maxIndex != node) {
        exchangeValue(node, maxIndex);
        maxHeap(length, maxIndex);
    }
}



/**
 *          
 *
 * @param first       
 * @param second      
 */
private void exchangeValue(int first, int second) {
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

時間複雑度O(nlogn)八、集計ソート
1、アルゴリズム思想
データセットを2つに分割する各グループが1つしか残っていないまで循環分割分割配列を並べ替える2つのマージは、1つの配列にマージされるまで、すなわちソートが完了するアルゴリズム思想参考下図2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ：         ，            
 */
private void mergeSort() {
    int[] temp = new int[array.length];
    mergeSort(temp, 0, array.length - 1);
}


/**
 *     ，         ，     ，      
 */
private void mergeSort(int[] temp, int start, int end) {

    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(temp, start, mid);
    mergeSort(temp, mid + 1, end);
    mergeArray(temp, start, mid + 1, end);
}


/**
 *    array， mid   ，          
 */
private void mergeArray(int[] temp, int start, int mid, int end) {

    //       ，             
    int minA = start, minB = mid;
    for (int i = start; i <= end; i++) {
        if (minA >= mid || minB > end) {
            //   a  b   ，       
            if (minA >= mid) {
                temp[i] = array[minB];
                minB++;
            } else {
                temp[i] = array[minA];
                minA++;
            }
        } else {
            //          
            if (array[minA] < array[minB]) {
                temp[i] = array[minA];
                minA++;
            } else {
                temp[i] = array[minB];
                minB++;
            }
        }
    }

    System.arraycopy(temp, start, array, start, end - start + 1);
}

時間複雑度O(nlogn)九、基数ソート
1、アルゴリズム思想
基数並べ替えはバケツ並べ替えとも呼ばれ、具体的には数値を配列の下標として保存することを考えている.
すべての数値をビットを取り出して比較する、例えば、値がmのものは、mと表記された配列のに格納される.
比較後の配列をビット順の配列として取り出し、この配列を10ビット順のとする.
10,000のすべてのビット数を比較すると、がソートされます.
ステップ一思想参考図2、コード例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 *     ，                 0-9      ，          
 *                      
 */
private void radixSort() {

    //                       
    int[][] temp;

    //                 
    int[] position;

    int radix = 1;

    while (true) {
        position = new int[10];
        temp = new int[10][array.length];

        for (int i = 0; i < array.length; i++) {
            int value = (array[i] / radix) % 10;
            temp[value][position[value]] = array[i];
            position[value]++;
        }

        //            0  ，  0         
        if (position[0] == array.length) {
            break;
        }

        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < position[i]; j++) {
                array[index] = temp[i][j];
                index++;
            }
        }

        radix = radix * 10;
    }
}

基数ソートの時間的複雑度はO(d(n+r)),rは基数,dはビット数である.
私は微信の公衆番号を持っていて、よくJava技術に関する干物を共有します.もし私の共有が好きなら、微信で「Java団長」や「javatuanzhang」を検索して注目することができます.
jmeter beanshell Type-d variable declaration:Object constructorエラー
hubotを使用してGithubのメンションされたコミットを通知する