排序思想:将n个待排序的元素看成一个有序表和一个无序表,开始时,有序表中只有一个元素,无序表中有n-1个元素,排序时,每次从无序表中取出第一个元素,把它依次与有序表中元素进行比较,将它插入到有序表中的适当位置,使之最后成为一个有序表。
编程思想:一般初始有序表就是arr[0],循环遍历设置待插入的数arr[i] 和它想插入的位置 i-1。
时间复杂度:O(n²)
public int[] insertSort(int [] arr){ for(int i=1; i < arr.length ; i++){ int insertVal = arr[i]; //待插入的值为arr[i] int insertIndex = i -1; // 待插入的位置,插到有序表前一位 // 待插入的值想一直往前插,要确保大于有序表中数据,且不能越过0 while( insertInde >=0 && insertvalue < arr[insertIndex]){ //一旦条件成立,有序表中元素后移,待插入的地方继续向前找 arr[inserIndex+1] = arr[insertIndex]; insertIndex --; } //一但跳出循环,说明已经找到了待插入的索引,不好想的话就想是插到末尾。索引得1+1 arr[insertIndex+1] = insertVal; } return arr; }