Detailed breakdown of 6 sorting algorithms commonly used in Java

The sorting algorithm is used in many places. I recently reviewed the algorithm again and simply implemented it myself. I hereby record it to save some material for future review.

Without further ado, let’s take a look at the classic sorting algorithms one by one:

1. Selection sorting

The basic idea of ​​selection sorting is that during the process of traversing the array, i Represents the current sequence number that needs to be sorted, you need to find the minimum value among the remaining [i...n-1], and then exchange the found minimum value with the value pointed by i. Because each process of determining elements will have a sub-process of selecting the maximum value, people vividly call it selection sorting. Let’s take an example:

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

i = 0: [2, 17 , 16, 16, 7, 31, 39, 32, 38, 11] (0th [38]e09be6022d700e04aeaa85a5f42fdcb28th [2])

i = 1: [2, 7, 16, 16 , 17 , 31, 39, 32, 38, 11] (1st [38]e09be6022d700e04aeaa85a5f42fdcb24th [17])

i = 2: [2, 7, 11 , 16, 17, 31 , 39, 32, 38, 16 ] (2nd [11]e09be6022d700e04aeaa85a5f42fdcb29th [16])

i = 3: [2, 7, 11, 16, 17, 31, 39, 32 , 38, 16] (no exchange required)

i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4th [17]e09be6022d700e04aeaa85a5f42fdcb2 9th [16])

i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5th [31]e09be6022d700e04aeaa85a5f42fdcb29th [17] )

i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6th [39]e09be6022d700e04aeaa85a5f42fdcb29th [31])

i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no exchange required)

i = 8: [2, 7, 11, 16 , 16, 17, 31, 32, 38, 39] (no exchange required)

i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no exchange required Exchange)

It can be seen from the example that as the sorting progresses (i gradually increases), the number of comparisons will become less and less. However, regardless of whether the array is initially ordered or not, the selection sorting will start from i. A selection comparison is performed to the end of the array, so for an array of a given length, the number of comparisons in selection sorting is fixed: 1 + 2 + 3 + …. + n = n * (n + 1) / 2, and the number of exchanges is It is related to the order of the initial array. If the initial array order is random, in the worst case, the array elements will be exchanged n times, and in the best case it may be 0 times (the array itself is ordered).

It can be deduced that the time complexity and space complexity of selection sort are O(n2) and O(1) respectively (selection sort only requires an extra space for array element exchange).

Implementation code:

/**  
* 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. Insertion sort

The basic idea of ​​insertion sort is that during the process of traversing the array, assume that the element before serial number i is [0. .i-1] have all been sorted. This time, we need to find the correct position k of the element "vacate the position", and finally assign the element value corresponding to k to x. Insertion sort is also named according to the characteristics of sorting.

The following is an example. The numbers marked in red are inserted numbers. The crossed-out numbers are elements that are not involved in this sorting. The elements between the numbers marked in red and the crossed-out numbers are the elements that are oriented one by one. The elements that are moved later, for example, the elements that participate in the second sorting are [11, 31, 12], and the element that needs to be inserted is 12, but 12 is not currently in the correct position, so we need to move it with the previous elements 31 and 11 in sequence. Compare, move the compared elements while comparing, and stop comparing when you find the first element 11 that is smaller than 12. At this time, the index 1 corresponding to 31 is the position where 12 needs to be inserted.

Initial: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]

First trip: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (no moving elements)

Second pass: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 to Move backward)

The third trip: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 all move backward)

The fourth trip: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (no moving elements)

The fifth trip: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] (31, 34 moves backward)

The sixth trip: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 moved backward)

The seventh pass: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (no moving elements)

The eighth trip: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 moves backward)

The ninth trip: [5, 11 , 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 move backward)

插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 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]e09be6022d700e04aeaa85a5f42fdcb28th [38 ）  
  
内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]e09be6022d700e04aeaa85a5f42fdcb27th [29] ）  
  
内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]e09be6022d700e04aeaa85a5f42fdcb26th [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]e09be6022d700e04aeaa85a5f42fdcb24th [36] ）  
  
内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]e09be6022d700e04aeaa85a5f42fdcb23rd [39] ）  
  
内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]e09be6022d700e04aeaa85a5f42fdcb22nd [26] ）  
  
内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]e09be6022d700e04aeaa85a5f42fdcb21st [19] ）  
  
内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]e09be6022d700e04aeaa85a5f42fdcb20th [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中文网！