插入排序

核心：通過構建有序序列，對于未排序序列，在已排序序列中從后向前掃描(對于單向鏈表則只能從前往后遍歷)，找到相應位置并插入。實現上通常使用in-place排序(需用到O(1)的額外空間)

1. 從第一個元素開始，該元素可認為已排序
2. 取下一個元素，對已排序數組從后往前掃描
3. 若從排序數組中取出的元素大于新元素，則移至下一位置
4. 重復步驟3，直至找到已排序元素小于或等于新元素的位置
5. 插入新元素至該位置
6. 重復2~5

public class InsertionSort {public static void main(String[] args) {int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};insertionSort(unsortedArray);System.out.println("After sort: ");for (int item : unsortedArray) {System.out.print(item + " ");}}public static void insertionSort(int[] array) {int len = array.length;for (int i = 0; i < len; i++) {int index = i, array_i = array[i];while (index > 0 && array[index - 1] > array_i) {array[index] = array[index - 1];index -= 1;}array[index] = array_i;/* print sort process */for (int item : array) {System.out.print(item + " ");}System.out.println();}}
}

輸出：

6 5 3 1 8 7 2 4 
5 6 3 1 8 7 2 4 
3 5 6 1 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 8 7 2 4 
1 3 5 6 7 8 2 4 
1 2 3 5 6 7 8 4 
1 2 3 4 5 6 7 8 
After sort: 
1 2 3 4 5 6 7 8

希爾排序

核心：基于插入排序，使數組中任意間隔為h的元素都是有序的，即將全部元素分為h個區域使用插入排序。其實現可類似于插入排序但使用不同增量。更高效的原因是它權衡了子數組的規模和有序性。

推薦大佬文章：排序算法 —— 希爾排序（圖文超詳細）

從網上搞了一個動圖

(圖網，侵刪)