Detaillierte Aufschlüsselung der 6 in Java häufig verwendeten Sortieralgorithmen

Der Sortieralgorithmus wird an vielen Stellen verwendet. Ich habe den Algorithmus kürzlich noch einmal überprüft und ihn hiermit aufgezeichnet, um etwas Material für eine zukünftige Überprüfung aufzubewahren.

Schauen wir uns ohne weiteres die klassischen Sortieralgorithmen einzeln an:

1 Auswahlsortierung

Die Grundidee der Auswahlsortierung ist das Durchlaufen Das Array mit i stellt die aktuelle Sequenznummer dar, die sortiert werden muss. Sie müssen den Mindestwert unter den verbleibenden [i ... n-1] finden und dann den gefundenen Mindestwert durch den Wert ersetzen, auf den i zeigt. Da jeder Prozess zum Bestimmen von Elementen einen Unterprozess zum Auswählen des Maximalwerts hat, wird dies im Volksmund auch als Auswahlsortierung bezeichnet. Nehmen wir ein Beispiel:

Initial: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]

i = 0: [2, 17 , 16 , 16, 7, 31, 39, 32, 38, 11] (0. [38]<->8. [2])

i = 1: [2, 7, 16, 16 , 17 , 31, 39, 32, 38, 11] (1. [38]<->4. [17])

i = 2: [2, 7, 11 , 16, 17, 31 , 39 , 32, 38, 16 ] (2. [11]<->9. [16])

i = 3: [2, 7, 11, 16, 17, 31, 39, 32 , 38 , 16] (kein Austausch erforderlich)

i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4. [17]<-> 9 [16])

i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5. [31]<->9. [17] )

i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6. [39]<->9. [31])

i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (kein Austausch erforderlich)

i = 8: [2, 7, 11, 16 , 16, 17, 31, 32, 38, 39] (kein Austausch erforderlich)

i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( kein Austausch erforderlich (Austausch)

Wie aus dem Beispiel ersichtlich ist, wird die Anzahl der Vergleiche mit fortschreitender Sortierung (i nimmt allmählich zu) immer geringer, aber unabhängig davon, ob das Array anfänglich geordnet ist, wird die Anzahl der Vergleiche immer geringer Die Auswahlsortierung beginnt bei i. Ein Auswahlvergleich wird bis zum Ende des Arrays durchgeführt. Für ein Array einer bestimmten Länge ist die Anzahl der Vergleiche bei der Auswahlsortierung also festgelegt: 1 + 2 + 3 + …. (n + 1) / 2, und die Anzahl der Austausche beträgt Es hängt von der Reihenfolge des anfänglichen Arrays ab. Wenn die anfängliche Array-Reihenfolge zufällig ist, werden die Array-Elemente im schlimmsten Fall n-mal ausgetauscht Im besten Fall kann es 0 Mal sein (das Array selbst ist geordnet).

Daraus lässt sich ableiten, dass die zeitliche Komplexität und die räumliche Komplexität der Auswahlsortierung O(n2) bzw. O(1) sind (die Auswahlsortierung erfordert nur zusätzlichen Platz für den Austausch von Array-Elementen).

Implementierungscode:

/**  
* Selection Sorting  
*/ 
SELECTION(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int len = array.length;  
        for (int i = 0; i < len; i++) {  
            int selected = i;  
            for (int j = i + 1; j < len; j++) {  
                int compare = array[j].compareTo(array[selected]);  
                if (compare != 0 && compare < 0 == ascend) {  
                    selected = j;  
                }  
            }  
  
            exchange(array, i, selected);  
        }  
    }  
})

2. Einfügungssortierung

Die Grundidee der Einfügungssortierung besteht darin, dass beim Durchlaufen des Arrays davon ausgegangen wird, dass das Element Bevor die Sequenznummer i [0..i-1] ist, wurden alle sortiert. Dieses Mal müssen wir die richtige Position k des Elements x finden, um die Position zu „räumen“ und schließlich den Elementwert zuzuweisen, der k entspricht . Die Einfügungssortierung wird auch nach den Sortiermerkmalen benannt.

Das Folgende ist ein Beispiel. Die durchgestrichenen Zahlen sind Elemente, die nicht an dieser Sortierung beteiligt sind Die Elemente, die später verschoben werden, sind beispielsweise [11, 31, 12], und das Element, das eingefügt werden muss, ist 12, aber 12 ist derzeit nicht vorhanden die richtige Position, also müssen wir es mit den vorherigen Elementen 31 und 11 nacheinander verschieben. Vergleichen und verschieben Sie den Vergleich, wenn Sie das erste Element 11 finden, das kleiner als 12 ist 1 entspricht 31 und ist die Position, an der 12 eingefügt werden muss.

Anfänglich: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]

Erste Fahrt: [11, 31, 12, 5, 34, 30 , 26, 38, 36, 18] (keine beweglichen Elemente)

Zweiter Durchgang: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 zum Zurückbewegen)

Der dritte Durchgang: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 bewegen sich alle rückwärts)

Der vierte Durchgang : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (keine beweglichen Elemente)

Der fünfte Durchgang: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] (31, 34 bewegt sich rückwärts)

Die sechste Fahrt: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31 , 34 nach hinten verschoben)

Siebter Trip: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (keine beweglichen Elemente)

Der achte Trip: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 bewegt sich rückwärts)

Die neunte Reise: [5, 11, 12, 18, 26, 30, 31 , 34, 36, 38] (26, 30, 31, 34, 36, 38 rückwärts bewegen)

插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。

实现代码：

/**  
* Insertion Sorting  
*/ 
INSERTION(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int len = array.length;  
        for (int i = 1; i < len; i++) {  
            T toInsert = array[i];  
            int j = i;  
            for (; j > 0; j–) {  
                int compare = array[j - 1].compareTo(toInsert);  
                if (compare == 0 || compare < 0 == ascend) {  
                    break;  
                }  
                array[j] = array[j - 1];  
            }  
  
            array[j] = toInsert;  
        }  
    }  
})

3. 冒泡排序

冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层 for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。

照例举个简单的实例吧：

初始状态： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]

内层第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] （ 9th [23]<->8th [38 ）

内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]<->7th [29] ）

内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]<->6th [31] ）

内层第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] （ 7 、 23 都位于正确的顺序，无需交换）

内层第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] （ 5th [7]<->4th [36] ）

内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]<->3rd [39] ）

内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]<->2nd [26] ）

内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]<->1st [19] ）

内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]<->0th [24] ）

……… .

其实冒泡排序跟选择排序比较相像，比较次数一样，都为 n * (n + 1) / 2 ，但是冒泡排序在挑选最小值的过程中会进行额外的交换（冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换），所以在我看来，选择排序属于冒泡排序的改进版。

实现代码：

/**  
* Bubble Sorting, it's very similar with Insertion Sorting  
*/ 
BUBBLE(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int length = array.length;  
        int lastExchangedIdx = 0;  
        for (int i = 0; i < length; i++) {  
            // mark the flag to identity whether exchange happened to false  
            boolean isExchanged = false;  
            // last compare and exchange happened before reaching index i  
            int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;  
            for (int j = length – 1; j > currOrderedIdx; j–) {  
                int compare = array[j - 1].compareTo(array[j]);  
                if (compare != 0 && compare > 0 == ascend) {  
                    exchange(array, j – 1, j);  
                    isExchanged = true;  
                    lastExchangedIdx = j;  
                }  
            }  
            // if no exchange happen means array is already in order  
            if (isExchanged == false) {  
                break;  
            }  
        }  
    }  
})

4. 希尔排序

希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ，则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。

具体实例请参照插入排序。

希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。

实现代码：

/**  
* Shell Sorting  
*/ 
SHELL(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        int length = array.length;  
        int gap = 1;  
  
        // use the most next to length / 3 as the first gap  
        while (gap < length / 3) {  
            gap = gap * 3 + 1;  
        }  
  
        while (gap >= 1) {  
            for (int i = gap; i < length; i++) {  
                T next = array[i];  
                int j = i;  
                while (j >= gap) {  
                    int compare = array[j - gap].compareTo(next);  
                    // already find its position  
                    if (compare == 0 || compare < 0 == ascend) {  
                        break;  
                    }  
  
                    array[j] = array[j - gap];  
                    j -= gap;  
                }  
                if (j != i) {  
                    array[j] = next;  
                }  
            }  
            gap /= 3;  
        }  
  
    }  
})

5. 归并排序

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下：

1） 将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；

2） 设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ，则 leftIdx = 0 （对应 copiedArray 中的第一个元素 [3] ）， rightIdx = 4 （对应 copiedArray 中的第五个元素 [1] ）；

3） 比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ，赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。

下面给个归并的具体实例：

第一趟：

辅助数组 [21 , 28, 39 | 35, 38] （数组被拆分为左右两个子数组，以 | 分隔开）

[21 , , , , ] （第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 ， i = 0 ）

第二趟：

辅助数组 [21, 28 , 39 | 35, 38]

[21 , 28, , , ] （第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 ， i = 1 ）

第三趟： [21, 28, 39 | 35 , 38]

[21 , 28 , 35, , ] （第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 ， i = 2 ）

第四趟： [21, 28, 39 | 35, 38 ]

[21 , 28 , 35 , 38, ] （第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 ， i = 3 ）

第五趟： [21, 28, 39 | 35, 38]

[21 , 28 , 35 , 38 , 39] （第五次时右边子数组已复制完，无需比较 leftIdx = 2 ， i = 4 ）
以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分（每次一分为二）直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序（由于采用递归）依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。

归并排序需要的额外空间是所有排序中最多的，每次归并需要与参与归并的两个数组长度之和相同个元素（为了提供辅助数组）。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 （忽略了 n 的奇偶性的判断），时间复杂度比较难估，这里小弟也忘记是多少了（囧）。

实现代码：

/**  
* Merge sorting  
*/ 
MERGE(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        this.sort(array, 0, array.length – 1, ascend);  
    }  
  
    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {  
        // OPTIMIZE ONE  
        // if the substring&#39;s length is less than 20,  
        // use insertion sort to reduce recursive invocation  
        if (hi – lo < 20) {  
            for (int i = lo + 1; i <= hi; i++) {  
                T toInsert = array[i];  
                int j = i;  
                for (; j > lo; j–) {  
                    int compare = array[j - 1].compareTo(toInsert);  
                    if (compare == 0 || compare < 0 == ascend) {  
                        break;  
                    }  
                    array[j] = array[j - 1];  
                }  
  
                array[j] = toInsert;  
            }  
  
            return;  
        }  
  
        int mid = lo + (hi – lo) / 2;  
        sort(array, lo, mid, ascend);  
        sort(array, mid + 1, hi, ascend);  
        merge(array, lo, mid, hi, ascend);  
    }  
  
    private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {  
        // OPTIMIZE TWO  
        // if it is already in right order, skip this merge  
        // since there&#39;s no need to do so  
        int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);  
        if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {  
            return;  
        }  
  
        @SuppressWarnings("unchecked")  
        T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];  
        System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);  
  
        int lowIdx = 0;  
        int highIdx = mid – lo + 1;  
  
        for (int i = lo; i <= hi; i++) {  
            if (lowIdx > mid – lo) {  
                // left sub array exhausted  
                array[i] = arrayCopy[highIdx++];  
            } else if (highIdx > hi – lo) {  
                // right sub array exhausted  
                array[i] = arrayCopy[lowIdx++];  
            } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {  
                array[i] = arrayCopy[lowIdx++];  
            } else {  
                array[i] = arrayCopy[highIdx++];  
            }  
        }  
    }  
})

6. 快速排序

快速排序也是用归并方法实现的一个“分而治之”的排序算法，它的魅力之处在于它能在每次 partition （排序算法的核心所在）都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。

更多Java中常用的6种排序算法详细分解相关文章请关注PHP中文网！