插入排序(Insertion sort)是一種簡(jiǎn)單直觀且穩(wěn)定的排序算法。
插入排序的工作方式非常像人們排序一手撲克牌一樣冶伞。開(kāi)始時(shí)唆香，我們的左手為空并且桌子上的牌面朝下。然后滑沧，我
們每次從桌子上拿走一張牌并將它插入左手中正確的位置并村。為了找到一張牌的正確位置，我們從右到左將它與已在
手中的每張牌進(jìn)行比較滓技，如下圖所示:
排序原理:
1.把所有的元素分為兩組哩牍，已經(jīng)排序的和未排序的; 2.找到未排序的組中的第一個(gè)元素，向已經(jīng)排序的組中進(jìn)行插入;
3.倒敘遍歷已經(jīng)排序的元素令漂，依次和待插入的元素進(jìn)行比較膝昆，直到找到一個(gè)元素小于等于待插入元素，那么就把待 插入元素放到這個(gè)位置洗显，其他的元素向后移動(dòng)一位;
代碼實(shí)現(xiàn)：
public static void insertionSort(int[] a) {
System.out.println("待排序數(shù)據(jù): " + Arrays.toString(a));
//這個(gè)是遍歷沒(méi)有排序的數(shù)組
for (int i = 1; i < a.length; i++) {
//這個(gè)是遍歷排序完成的數(shù)組外潜，拿待排序的數(shù)據(jù)依次和排好的數(shù)組元素比較交換，這里就和冒泡排序一樣了
for (int j = i; j > 0; j--) {
if (a[j - 1] > a[j]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
} else {
break;//找到了合適的位置挠唆，不需要再比較，結(jié)束循環(huán)
}
}
System.out.println("第" + (i) + "輪排序后的數(shù)組為: " + Arrays.toString(a));
}
}
插入排序的時(shí)間復(fù)雜度分析：
插入排序使用了雙層for循環(huán)嘱吗，其中內(nèi)層循環(huán)的循環(huán)體是真正完成排序的代碼玄组，所以滔驾，我們分析插入排序的時(shí)間復(fù) 雜度，主要分析一下內(nèi)層循環(huán)體的執(zhí)行次數(shù)即可俄讹。
最壞情況哆致，也就是待排序的數(shù)組元素為{12,10,6,5,4,3,2,1}，那么: 比較的次數(shù)為: (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2; 交換的次數(shù)為: (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2; 總執(zhí)行次數(shù)為:
(N^2/ 2-N/2)+(N^2/ 2-N/2)=N^2-N; 按照大O推導(dǎo)法則患膛，保留函數(shù)中的最高階項(xiàng)那么最終插入排序的時(shí)間復(fù)雜度為O(N^2).
