Java中常用的6種排序演算法詳細分解

排序演算法很多地方都會用到，近期又重新看了一遍演算法，並自己簡單地實現了一遍，特此記錄下來，為以後複習留點材料。

廢話不多說，下面逐一看看經典的排序演算法：

1. 選擇排序

選擇排序的基本思想是遍歷數組的過程中，以i 代表當前需要排序的序號，則需要在剩餘的[i…n-1] 中找出其中的最小值，然後將找到的最小值與i 指向的值交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形像地稱之為選擇排序。舉個實例來看：

初始： [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]  
  
i = 0:  [2 , 17, 16, 136, 1313,1313, 136,1313,1313,1313, 136 , 39, 32, 38 , 11] (0th [38]8th [2])  
  
i = 1:  [2, 7 , 16, 16, 17 , 31, 39, 2, 38, 1] (38, 1] (38 1st [38]4th [17])  
  
i = 2:  [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11] ])  
  
i = 3:  [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 無需交換)  
 31, 39, 32, 38, 17 ] (4th [17]9th [16])  
  
i = 5:  [2, 7, 11, 16, 16, 17 , 39, 2, 398, 2, 33 ] (5th [31]9th [17])  
  
i = 6:  [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]9th [39]9th [39] 31])  
  
i = 7:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( , 17, 31, 32, 38, 39] ( 無需交換)  
  
i = 9:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (可以看出，選擇排序隨著排序的進行（ i 逐漸增大），比較的次數會越來越少，但是不論數組初始是否有序，選擇排序都會從i 至數組末尾進行一次選擇比較，所以給定長度的數組，選擇排序的比較次數是固定的： 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ，而交換的次數則跟初始數組的順序有關，如果初始數組順序為隨機，則在最壞情況下，數組元素將會交換n 次，最好的情況下則可能0 次（數組本身即為有序）。

由此可以推出，選擇排序的時間複雜度和空間複雜度分別為 O(n2 ) 和 O(1) （選擇排序只需要一個額外空間用於數組元素交換）。

實現代碼：

/**  
* 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. 插入排序

插入排序的基本思想是在遍歷數組的過程中，假設在序號i 之前的元素即[0..i-1] 都已經排好序，本趟需要找到i 對應的元素x 的正確位置k ，並且在尋找這個位置k 的過程中逐個將比較過的元素往後移一位，為元素x “騰位置”，最後將k 對應的元素值賦為x ，插入排序也是根據排序的特性來命名的。

以下是一個實例，紅色標記的數字為插入的數字，被劃掉的數字是未參與此次排序的元素，紅色標記的數字與被劃掉數字之間的元素為逐個向後移動的元素，例如第二趟參與排序的元素為[11, 31, 12] ，需要插入的元素為12 ，但是12 當前並沒有處於正確的位置，於是我們需要依次與前面的元素31 、 11 做比較，一邊比較一邊移動比較過的元素，直到找到第一個比12 小的元素11 時停止比較，此時31 對應的索引1 則是12 需要插入的位置。

初始：    [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]  

  

第一班： [11, 31 , 12, 5,363, 36, 36, 36, 36, 36 18] （無移動的元素）  

  

第二班： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] （ 31 向後移動）  

：  11, 12, 31, 34, 30, 26, 38, 36, 18] （ 11, 12, 31 皆向後移動）  
  
第四班： [5, 11, 12, 31, 344 6,0344 38, 36, 18] （無移動的元素）  
  
第五班： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] （ 31, 34 向後移動🠎)六趟： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] （ 30, 31, 34 向後移動）  
  
第七班： [5, 11, 1230, , 31, 34, 38 , 36, 18] （無移動的元素）  
  
第八趟： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] （後移 38）
  
第九趟： [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] （ 26, 30, 31, 34, 36, 38 向後移動）

插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 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中文网！