插入排序之直接插入排序

基本思路：将一个记录插入到已经排好序的有序表中，得到一个新的记录数加1的有序表。通过对未排序的数据执行逐个插入至合适位置而完成排序工作。
步骤：
（1）将整个待排序序列划分为有序区和无序区，初始化有序区为待排序记录序列中的第一个，无序区包括所有剩余的待排序记录；
（2）无序区的第一个记录插入到有序区的合适位置，无序区减一个记录，有序区加一个记录；
（3）不断重复（2），直至无序区没有记录为止。

直接插入排序图解

代码如下：

public class Insertion_Sort {
    
    
    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int[] st = {1,3,2,5,4,4,4,4,4,4,5,5,5,5,5,5,5,1,1,1,1,2,2,2,3,4,5,7,3,2,2,24,54};
        sort1(st);
//      sort2(st);
        long endTime=System.nanoTime();     //获取结束时间
        System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
        System.out.println(Arrays.toString(st));
    }
    
    //程序运行时间： 20128ms
    public static void sort1(int[] a){
        for(int i = 1; i < a.length; i++){ //从第2个数字开始排序。第一个数组作为有序数组
            for(int j = i-1; j >= 0; j--,i--){
                if(a[i] < a[j]){ //如果当前数字小于有序数组的最后一位，则往前移动
                    int temp = a[i]; 
                    a[i] = a[j];   
                    a[j] = temp;        
                }else{
                    break;
                }
            }
        }
    }
    
    //程序运行时间：11711ms
    public static void sort2(int[] b){
        int i , j , key;
        for(i=1;i<b.length;i++){
            key = b[i];
            for(j = i-1; j>=0; j--){
                if(b[j]>key){
                    b[j+1]=b[j];
                }else{
                    break;
                }
            }
            b[j+1] = key;
        }
    }       
}