排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料，
Java实现的常用排序算法详细解读
。废话不多说，下面逐一看看经典的排序算法：
1、选择排序
选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。
举个实例来看看：
1.初始： [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
2.3.i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] （0th [38]<->8th [2]）
4.5.i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] （1st [38]<->4th [17]）
6.7.i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] （2nd [11]<->9th [16]）
8.9.i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] （ 无需交换 ）
10.11.i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] （4th [17]<->9th [16]）
12.13.i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] （5th [31]<->9th [17]）
14.15.i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] （6th [39]<->9th [31]）
16.17.i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] （ 无需交换 ）
18.19.i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] （ 无需交换 ）
20.21.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）（选择排序只需要一个额外空间用于数组元素交换）。
实现代码：
1./**
2. * Selection Sorting
3. */
4.SELECTION（new Sortable（） {
5. public 6. int len = array.length; 7. for （int i = 0; i < len; i++） { 8. int selected = i; 9. for （int j = i + 1; j < len; j++） { 10. int compare = array[j].compareTo（array[selected]）； 11. if （compare != 0 && compare < 0 == ascend） { 12. selected = j; 13. } 14. } 15.16. exchange（array, i, selected）； 17. } 18. } 19.}） 2、插入排序 插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x "腾位置",最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的，电脑资料
《Java实现的常用排序算法详细解读》(https://www.unjs.com)。
以下是一个实例，红色 标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置，于是我们需要依次与前面的元素 31 、 11 做比较，一边比较一边移动比较过的元素，直到找到第一个比 12 小的元素 11 时停止比较，此时 31 对应的索引 1 则是 12 需要插入的位置。
1.初始： [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
2.3.第一趟： [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] （无移动的元素）
4.5.第二趟： [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] （ 31 向后移动）
6.7.第三趟： [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] （ 11, 12, 31 皆向后移动）
8.9.第四趟： [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] （无移动的元素）
10.11.第五趟： [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] （ 31, 34 向后移动）
12.13.第六趟： [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] （ 30, 31, 34 向后移动）
14.15.第七趟： [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] （无移动的元素）
16.17.第八趟： [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] （ 38 向后移动）
18.19.第九趟： [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） .
实现代码：
1./**
2. * Insertion Sorting
3. */
4.INSERTION（new Sortable（） {
5. public