1 直接插入排序

1.1 算法思想

插入排序的基本思想是：每一趟将1个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

1.2 算法特征

属于【插入排序】

直接插入排序
折半插入排序
希尔排序
适用于【稳定性】：稳定
适用于【规模N】：较小
适用于【有序性】：有序
适用于【存储结构】：顺序存储or链式存储（二者均可）
【时间复杂度】：O(N)(最好) / O(NN) (平均) / O(NN) (最坏)
【空间复杂度】：O(1) (最好/平均/最坏)
相关口诀：【插冒归堆】好有序，【插冒】记录个数小，【插冒二选】时N方

1.3 算法实现

import java.util.Arrays;

public class InsertSort {//直接插入排序 - 升序

    public static int [] insertSort(int [] array){

        int [] resultArray = Arrays.copyOfRange(array, 0, array.length);

        int insertingEleValue,j;

        for(int i=1;i<resultArray.length;i++){

            if(resultArray[i-1] > resultArray[i]){ //前面已排序部分的最后1个元素比当前i元素还大时

                insertingEleValue = resultArray[i];//待插入的元素值

                for(j=i-1;j>=0&&resultArray[j]>insertingEleValue;j--){//j>=0:防止j越界；resultArray[j]>insertingEleValue：后移的必备条件

                        resultArray[j+1] = resultArray[j];

                }

                resultArray[j+1] = insertingEleValue;//for循环中多减了1，故补上1

            }

        }

        return resultArray;

    }

}

1.4 测试实现

import java.util.Scanner;

public class Main {

    public static void print(int[] array){

        if(array==null || array.length<1){

            return;

        }

        for(int i=0;i<array.length-1;i++){

            System.out.print(array[i]+" ");

        }

        System.out.println(array[array.length-1]);

    }

    public static void main(String[] args) {

        //1 输入 一组 乱序的数值 数组

        Scanner scanner = new Scanner(System.in);

        String input = scanner.nextLine();

        String [] strValues = input.trim().split(" ");

        int [] array = new int[strValues.length];

        for(int i=0,len=strValues.length;i<len;i++){

            array[i] = Integer.valueOf(strValues[i]).intValue();//假定所有输入均为合规的整型数值

        }

//        print(array);// test - 输出 所输入的数据

        //2 排序

        int [] sortedArray = InsertSort.insertSort(array);

        //3 输出

        print(sortedArray);

    }

}

1.5 参考文献

《数据结构（C语言-第2版-严蔚敏 吴伟民 著）》：Page237

[Java]排序算法>插入排序>【直接插入排序】(O(N*N)/稳定/N较小/有序/顺序存储+链式存储)的相关教程结束。