• 插入排序

  把第一个数当做有序数列，第二个到最后当做无序数列，开始扫描比较，每次将选择有序数列后一个数开始与有序数列比较，当比较到当前数大于时候有序数时，则插入，循环往复。

$时间度为O(n^2)$

package top.ltyzqhh.Annotation;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a={234,334,532,1313,1,3,553};
        System.out.println(Arrays.toString(a));
        insertionSort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void insertionSort(int[] array){
        //外层循环，判断我们这个要走多少次；
        for (int i = 1; i <array.length; i++) {
           int temp=array[i];
           int tempindex=i;
          //内层循环，判断如果这个数比前一个小的话则交换直到不能交换为止
            // 这个tempindex-1>=0条件要先于temp<array[tempindex-1]，不然会先执行temp<array[tempindex-1]，导致坐标越界
           while( tempindex-1>=0 && temp<array[tempindex-1] ){
                   array[tempindex]=array[tempindex-1];
                   tempindex--;
            }
           array[tempindex] =temp;
        }

    }
}