[数据结构与算法]插入排序 java

原理

图

基本思想

??将一个待排序序列左边看出有序区，右边看成无序区，每次取无序区(右边)第一个数，在左边有序区寻找其所在的位置。
??例如上图
??1)17 看作有序区，其他数看作无序区，无序区第一个数字3，因为小于17，所以放在左边。
??2）3、17看成有序去，其他数看作无序区，无序区第一个数字25，因为大于17，所以放在右边。
??…

代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] array = {101,34,119,1,50,-1};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void insertSort(int[] array){
       for (int i = 1;i < array.length;i++){
           int value = array[i];    //记录无序区第一个数字
           int valueIndex = i - 1;  //记录有序区索引
           //循环遍历插入无序区第一个数字放在有序区的位置
           while (valueIndex >= 0 && value < array[valueIndex]){
               array[valueIndex + 1] = array[valueIndex];//后移
               valueIndex--;
           }
           //如果不是
           if (valueIndex + 1 != i){
               array[valueIndex + 1] = value;
           }
       }
    }
}

声明

??本文是作者在学习数据结构中的一些笔记，希望能够帮助到大家。作者才疏学浅，如有错误，欢迎批评指正。