基本思想
??????直接插入排序是將一個(gè)記錄插入到已經(jīng)排好序的有序表中趾唱，從而得到一個(gè)新的記錄數(shù)增1的有序表。
直接插入排序算法
void insertSort(int[] array) {
int length = array.length;
int j = 0;
for (int i = 1; i < length; i++) {
if (array[i - 1] > array[i]) {
int tmp = array[i];
j = i - 1;
for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
array[j + 1] = array[j];
}
array[j + 1] = tmp;
}
}
}
直接插入排序算法的時(shí)間復(fù)雜度
??????最好情況下蜻懦，排序表本身就是有序的，比較記錄是n-1次夕晓，沒有移動(dòng)記錄宛乃，時(shí)間復(fù)雜度O(n)。
??????最壞情況下蒸辆，排序表本事是逆序的征炼，比較記錄是2+3+······+n次，也就是(n+2)(n-1)/2次躬贡，記錄的移動(dòng)次數(shù)也達(dá)到最大值3+4+······+(n+1)次谆奥，也就是(n+4)(n-1)/2次。
??????若排序記錄是隨機(jī)的拂玻，根據(jù)概率相同原則酸些，平均比較和移動(dòng)次數(shù)約為(n2)/4，所以直接插入排序的時(shí)間復(fù)雜度為O(n2)檐蚜。
