001什么是插入排序？

1）插入排序是把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重復n-1次可完成排序過程。

2）具體流程如下：

【1】把數組分成有序a[0]和無序a[1~7]范圍，有序中就一個數肯定是有序的不用管。

【2】把數組分成有序a[0~1]和無序a[2~7]范圍，有序中讓a[1]和a[0]范圍比較，如果a[1]大于a[0],不用交換；如果a[1]小于a[0],交換位置，這樣a[0~1]就是有序的。

【3】把數組分成有序a[0~2]和無序a[3~7]范圍，有序中讓a[2]和a[0~1]范圍比較。如果a[2]大于a[1],不用交換；如果a[2]小于a[1],交換位置；周而復始再讓a[1]和a[0]比較，這樣a[0~2]就是有序的。

【4】把數組分成有序a[0~3]和無序a[4~7]范圍，有序中讓a[3]和a[0~2]范圍比較。如果a[3]大于a[2],不用交換；如果a[3]小于a[2],交換位置；周而復始再讓a[2]和a[1]比較........這樣a[0~3]就是有序的。

【5】把數組分成有序a[0~4]和無序a[5~7]范圍，有序中讓a[4]和a[0~3]范圍比較。如果a[4]大于a[3],不用交換；如果a[4]小于a[3],交換位置；周而復始再讓a[3]和a[2]比較........這樣a[0~4]就是有序的。

...... 就這樣依次比較到最后一個元素，通俗的說就是一路向左交換。

002插入排序的代碼實現？

public static void insertSort(int[ ] arr){
    if(arr==null||arr.length<2){
        return;
    }
    //0~0有序的
    //0~i有序
    for(int i=1;i<arr.length;i++){
        for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
            swap(arr,j,j+1);
        }
    }
}

003設一組初始記錄關鍵字的長度為8，則最多經過( )趟插入排序可以得到有序序列。

A. 6
B. 7
C. 8
D. 9
答案：B
解析：第i趟插入排序可以使前i個元素為n個元素中前i小且有序，執行n-1次后前n-1個元素為n個元素中前n-1小且有序，第n個元素同時也處于正確的位置，故只需n-1趟插入排序。