插入排序

class InsertSort {

/*

插入排序，是将待排序数组(包含n个元素)，看成是一个有序数组和一个无序数组

将无序数组插入到有序数组合适的位置

开始有序数组只包含一个元素，无序数组包含n-1个元素

*/

    public static void main(String argv[]){

        int[] arr = {12,8,9,4,10,3,1,6};

        System.out.println("Before Sort：");

        for (int i=0;i<arr.length;i++){

            System.out.println(arr[i]);

        }

        System.out.println("After Sort：");

        sort(arr);

        for(int i=0;i<arr.length;i++){

            System.out.println(arr[i]);

        }

    }

    public static void sort(int[] arr){

        //外层循环，从1开始，将第0个元素看成是有序数组的元素

        for(int i = 1;i<arr.length;i++){

            //indexValue准备和前一个元素进行比较

            int indexValue = arr[i];//哨兵

            int index = i-1;

            //while循环（因为不知道次数，所以使用while循环，index用来做跳出while标志）

            //当arr[i-1]>arr[i]时，进行插入炒作

            while(index>=0 && indexValue<arr[index]){

                arr[index+1]=arr[index];

                index--;

            }

            //将哨兵插入到合适的位置（注意此处的也需要index+1,因为在while循环中有index--）

            arr[index+1] = indexValue;

        }

    }

}

代码实现