插入排序思路:
对于一个乱序的数组 5,1,2,7,3,9,8,11,4,我们可以分成两个数组,一个有序数组,一个无序数组,我们从无序数组中取出数字插入到有序数组当中,以这个数组为例,我们可以假设5是有序数组,其余是无序数组,即
有序数组 5
无序数组 1,2,7,3,9,8,11,4
然后我们从无序数组取出第一个 也就是1与有序数组进行比较, 可以看出有序数组的最后一个数字的下标与无序数组的第一个数字的下标是挨着的
当我们进行插入之前,首先要将有序数组的长度加一,这时候5先向后移动一位,将本身的位置空出来,如果待插入的数字小于5那么插入到5前面,如果待插入的数字大于5,则覆盖掉后移5
开始只有一个5,要插入的时候5先向后移一位,有序数组变成 5,5
比较大小看待插入的数字放置的位置比如说插入的是1那么就覆盖掉前一个5,变成1,5,代码如下
public class Insert { public static void main(String[] args){ int[] a={ 5,1,2,7,3,9,8,11,4}; System.out .println(Arrays.toString(insert(a))); } public static int[] insert(int[] arr){ int b=arr.length; for(int i=1;i<b;i++){//遍历无序数组里面的所有数字 int tem=arr[i];//从无序数组取出来的数字 int j; for(j=i-1;j>=0&&tem<arr[j];j--){ //j是有序数组的最后一个下标,也是有序数组最大的数字的下标,当取出的无序数组中的数字比有序数组最大的还小的时候,我们要往前找,找到插入的位置 arr[j+1]=arr[j]; } //如果插入的数字比最大的还要大,那么有序数组长度加一,将最大的数字放在最后,注意上面的for循环已经先--了,所以我们要用的时候要++ arr[j+1]=tem; } return arr; } }