1. 基本定義
插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。
插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過(guò)構(gòu)建有序序列坟岔，對(duì)于未排序數(shù)據(jù)豫缨，在已排序序列中從后向前掃描独令，找到相應(yīng)位置并插入。
插入排序和冒泡排序一樣好芭，也有一種優(yōu)化算法燃箭，叫做拆半插入。
- 算法步驟
將第一待排序序列第一個(gè)元素看做一個(gè)有序序列舍败，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列招狸。
從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置邻薯。（如果待插入的元素與有序序列中的某個(gè)元素相等裙戏，則將待插入元素插入到相等元素的后面。）
2. 代碼
public static void main(String[] args) {
int[] arr = {3,5,8,6,2,4,9};
int[] sortArr = sort(arr);
for (int c : sortArr) {
System.out.println(c);
}
}
public static int[] sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 記錄要插入的數(shù)據(jù)
int tmp = arr[i];
// 從已經(jīng)排序的序列最右邊的開(kāi)始比較厕诡，找到比其小的數(shù)
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的數(shù)累榜，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
