数据结构与算法05 插入排序

基本概念

插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它与有序表元素进行比较，将它插入到有序表中的适当位置，生成新的有序表。

JAVA代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89};
        InsertSort.insertSort(arr);
    }

    public static void insertSort(int[] arr){
        int insertValue;
        int insertIndex;
        for(int i = 1; i < arr.length; i++){
            insertValue = arr[i];
            insertIndex = i - 1;//待插入的坐标
            while(insertIndex >= 0 && arr[insertIndex] > insertValue){
                arr[insertIndex + 1] = arr[insertIndex];
//                arr[insertIndex] = insertValue; //效率不高，放在下面
                insertIndex--;
            }
            arr[insertIndex + 1] = insertValue;

            System.out.println("第" + i +"轮插入");
            System.out.println(Arrays.toString(arr));
        }

    }
}