插入排序算法

（1）概念：通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應的位置并插入。

（2）一個通俗的比喻：

插入排序就類似于斗地主時，整理撲克牌的情況。第一次摸牌時，左收是空的，之后每次摸牌插入到左手的牌時，都會將這張牌和左手中已經排好序的牌，從右到左比較，確認這張牌該放的位置。

示例代碼：

public static void insertionSort(int arr[]) {for (int i = 1; i < arr.length; i++) {//插入的數int insertVal = arr[i];//被插入的位置(準備和前一個數比較)int index = i - 1;//如果插入的數比被插入的數小while (index >= 0 && insertVal < arr[index]) {//將把 arr[index] 向后移動arr[index + 1] = arr[index];//讓 index 向前移動index--;}//把插入的數放入合適位置arr[index + 1] = insertVal;}
}