插入排序面试题

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趟插入排序。