插入排序

1.算法步骤

　　将第一个待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列.

　　从头到尾一次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置.(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面).

2.举例说明

　　(1)直接插入排序

　　

现有一个无序数组，共7个数：89 45 54 29 90 34 68。

使用直接插入排序法，对这个数组进行升序排序。

　　89 45 54 29 90 34 68

　　45 89 54 29 90 34 68

　　45 54 89 29 90 34 68

　　29 45 54 89 90 34 68

　　29 45 54 89 90 34 68

　　29 34 45 54 89 90 68

　　29 34 45 54 68 89 90

3.代码展示

//java代码实现---插入排序
public class InsertSort implements IArraySort{

    @Override
    public int[] sort(int[] sourceArray) {
        //对arr进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
        //从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个
        
        for(int i = 1;i < arr.length ; i++){
            
            //记录要插入的数据
            int tmp = arr[i];
            
            //从已经排序的序列最右边的开始比较,找到比其小的数
            
            int j = i;
            while(j > 0 && tmp < arr[j-1]){
                arr[j] = arr[j-1];
                j--;
            }
            //存在比其小的数,插入
            if(j!=i){
                arr[j] = tmp;
            }
        }
        return arr;
        
    }

}