1、 稳定性（重要）
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的算法。
直接插入排序：
时间复杂度：最好O(N);
最坏：O(N^2)
空间复杂度：O(1).
| public static void insertSort(int[] array) { | ||
| 16 | for (int i = 1; i < array.length; i++) { | |
| 17 | int tmp = array[i]; | |
| 18 | int j = i - 1; | |
| 19 | for (; j >= 0 ; j--) { | |
| 20 | if (array[j] > tmp) { | |
| 21 | array[j + 1] = array[j]; | |
| 22 | }else{ | |
| 23 | break; | |
| 24 | } | |
| 25 | } | |
| 26 | array[j + 1] = tmp; | |
| 27 | } | |
| 28 | } |
希尔排序：
时间复杂度O（n^1.3-n^1.5)
空间复杂度O（1）
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
| public static void shellSort(int[]array) {//希尔排序，时间复杂度O（n^1.3-n^1.5) | ||
| 6 | int [] ret = {5,3,1}; | |
| 7 | for (int i = 0; i < ret.length; i++) { | |
| 8 | shell(array,ret[i]); | |
| 9 | } | |
| 10 | } | |
| 11 | public static void shell(int[]array,int gap) { | |
| 12 | for (int i = gap; i < array.length ; i++) { | |
| 13 | int tmp = array[i]; | |
| 14 | int j = i - gap; | |
| 15 | for (; j >= 0 ; j-= gap) { | |
| 16 | if (array[j] > tmp) { | |
| 17 | array[j + gap] = array[j]; | |
| 18 | }else{ | |
| 19 | break; | |
| 20 | } | |
| 21 | } | |
| 22 | array[j + gap] = tmp; | |
| 23 | } | |
| 24 | } |
