原理
口語描述：第二個和第一個比松申，從小到大排云芦。第三個和第二個比，再和第一個比贸桶，從小到大排舅逸。第四個和第三個、第二個皇筛、第一個比琉历，從小到大排。水醋。旗笔。。拄踪。
數(shù)組a[n]蝇恶，lenght=n
從a[1] 開始到a[n-1]結束和之前的值進行比較，按從小到大的順序排惶桐。
a[1]和a[0]比較撮弧，若a[1] < a[0]，交換a[1] 和 a[0]姚糊。
a[0]-a[1]已經(jīng)排好序贿衍，讓a[2]和a[1]比較，
①若a[2] < a[1]救恨，則交換a[2] 和 a[1]贸辈，再比較a[1]和a[0]，若a[1]< a[0]則交換忿薇。
②若a[2]不小于a[1]則不動裙椭。
這時a[0],a[1],a[2]已經(jīng)排好序。
接著輪到a[3]和前面的a[0],a[1],a[2]作比較署浩，發(fā)現(xiàn)比自己大的就交換揉燃。一直輪到a[n-1]
代碼
//插入排序
public class Sort03 {
public static void main(String[] args) {
int[] array = { 2, 15, 7, 9, 30, 1, 5 };
insertSort(array);
for (int i : array) {
System.out.print(i+" ");
}
}
/**
* 數(shù)組a[n], lenght=n
* 按照最壞的情況計算
* i∈[1,n-1]
* i=1時j∈[1],循環(huán)1次
* i=2時j∈[2,1],循環(huán)2次
* i=n-1時j∈[n-1,1],循環(huán)n-1次
*
* 所以，當數(shù)組長度為n時筋栋，內(nèi)層循環(huán)執(zhí)行的次數(shù)=swap()方法執(zhí)行的次數(shù)炊汤，為(n2-n)/2
* 時間復雜度為O(n2)
*/
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) {
swap(array, j, j - 1);
} else {
break;
}
}
}
}
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
輸出結果
1 2 5 7 9 15 30
