Introduce

image.png

思想

image.png

将数组看做两个数组，一个有序，一个无序，从索引为1的位置开始遍历，当前值和有序数组中的元素进行比较，并同时完成有序数组的扩张，如果当前值小于有序数组中的元素，则该元素右移，找到要插入的索引位。

时间复杂度

最好 O(n)，最坏 O(n(n-1)) O（n^2）
code

package com.pl.arithmetic.sort;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BubbleSort
 * @Author pl
 * @Date 2020/11/29
 * @Version V1.0.0
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));


        /*int[] arr = new int[80000];
        for(int i =0; i < 80000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }
        Instant befor = Instant.now();
        selectSort(arr);
        Instant after = Instant.now();
        Duration between = Duration.between(befor, after);
        System.out.println(between.toMillis());*/
    }



    public static void insertSort(int[] arr){
        //有序数组中的索引位
        int orderlyArrIndex = 0;
        int insertValue = 0;
        for (int i = 1; i < arr.length; i++) {
            orderlyArrIndex = i-1;
            insertValue = arr[i];
            //寻找索引位的前一位，并完成有序数组的扩张，当前值和有序数组中的元素进行比较，若小于某个元素，则该元素右移。
            while (orderlyArrIndex >= 0 && insertValue < arr[orderlyArrIndex]){
                arr[orderlyArrIndex+1] = arr[orderlyArrIndex];
                orderlyArrIndex--;
            }
            //判断要插入的索引位 orderlyArrIndex+1 是否需要插入替换
            if (orderlyArrIndex+1 != i){
                arr[orderlyArrIndex+1] = insertValue;
            }

        }
    }
}

image.png

80000排序

package com.pl.arithmetic.sort;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName BubbleSort
 * @Author pl
 * @Date 2020/11/29
 * @Version V1.0.0
 */
public class InsertSort {

    public static void main(String[] args) {
      /*  int[] arr = {101, 34, 119, 1, -1, 89};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));*/


        int[] arr = new int[80000];
        for(int i =0; i < 80000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }
        Instant befor = Instant.now();
        insertSort(arr);
        Instant after = Instant.now();
        Duration between = Duration.between(befor, after);
        System.out.println(between.toMillis());
    }



    public static void insertSort(int[] arr){
        //有序数组中的索引位
        int orderlyArrIndex = 0;
        int insertValue = 0;
        for (int i = 1; i < arr.length; i++) {
            orderlyArrIndex = i-1;
            insertValue = arr[i];
            //寻找索引位的前一位，并完成有序数组的扩张，当前值和有序数组中的元素进行比较，若小于某个元素，则该元素右移。
            while (orderlyArrIndex >= 0 && insertValue < arr[orderlyArrIndex]){
                arr[orderlyArrIndex+1] = arr[orderlyArrIndex];
                orderlyArrIndex--;
            }
            //判断要插入的索引位 orderlyArrIndex+1 是否需要插入替换
            if (orderlyArrIndex+1 != i){
                arr[orderlyArrIndex+1] = insertValue;
            }

        }
    }
}

image.png

546毫秒，比选择排序还快。