考研時候復(fù)習(xí)嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)症见，發(fā)現(xiàn)還有好多自己不會的東西，甚至連插入排序都忘了捺弦。特別尷尬饮寞。
插入排序的思路很簡單孝扛，假設(shè)該數(shù)字前的數(shù)組已經(jīng)是排好序了的，再將這個數(shù)字插入到合適的位置幽崩，再將后面的元素往后移一位苦始。
比如4 1 9 7 20 3 5這樣一個數(shù)組
第一趟排序后：1 4 9 7 20 3 5
第二趟排序后：1 4 9 7 20 3 5
第三趟排序后：1 4 7 9 20 3 5
第三趟排序后：1 4 7 9 20 3 5
第四趟排序后：1 3 4 7 9 20 5
第五趟排序后：1 3 4 5 7 9 20
具體算法如下：
public static void insertSort(int[] nums) {
int i, j, temp;
for (i = 1; i < nums.length; i++) {
temp = nums[i];
for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
nums[j + 1] = nums[j];
}
nums[j + 1] = temp;
}
}
代碼應(yīng)該非常好懂，不需要做贅述了慌申。
