插入排序

一、分类

1、直接插入排序
2、希尔插入排序

1、直接插入排序

A.含义

讲一个记录插入到已经排序好的有序列表当中。

B.步骤

a.sorted数组的第0个位置没有放入数据
b.从sorted第二个数据开始处理:如果该数据比前面的数据小.说明该数据需要往前面移动。
    （1）首先将该数据备份到 sorted的0号位置作为"哨兵"
    （2）然后将该数据的前面那个数据往后移动
    （3）然后往前搜索，找插入的位置
    （4）找到插入的位置之后，第0位置的那个数据插入到对应的位置。

直接插入排序.PNG

2、希尔排序（缩小增量排序 diminishing increment sort）

A.含义

先将整个等待排序的代码分割成为若干的子序列，分别进行直接插入排序，等待整个序列中记录基本有序的时候，再对全体进行一次直接插入排序

B.插入排序代码

main()方法的写法

public static void main(String[] args) {
    Random r = new Random();
    int size = 10;
    int[] array = new int[size];
    //排序前,赋值并且打印
    System.out.println("排序前:");
    for (int i = 0; i < array.length; i++) {
        array[i] = r.nextInt(100);
        System.out.print(array[i]+" ");
    }
    System.out.println();
    //调用排序方法
    insertSort(array);
    //排序后,打印输出结果
    System.out.println("排序后:");
    for (int i = 1; i < array.length; i++) {
        System.out.print(array[i]+" ");
    }
    System.out.println();
}

排序方法的写法

//直接插入排序的方法
public static void insertSort(int[] arr){
    int len = arr.length;
    for (int i = 2; i < len; i++) {
        if(arr[i]<arr[i-1]){
            arr[0] = arr[i];
            arr[i] = arr[i-1];
            int insertPosition = 0;
            for (int j = i-2; j >=0; j--) {
                if (arr[j]>arr[0]){
                    arr[j+1] = arr[j];
                }else{
                    insertPosition = j+1;
                    break;
                }
            }
            arr[insertPosition] = arr[0];
        }
    }
}

运行结果

排序前:
2 68 46 58 81 61 18 27 54 43 
排序后:
18 27 43 46 54 58 61 68 81