1、简单介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

2、源码

  1. package com.study.sort;
  3. import java.util.Arrays;
  5. public class InsertSort {
  7.     public static void main(String[] args) {
  8.         int[] arr = {50,40,101,34,99,1};
  9.         insertSort(arr);
  10.     }
  12.     public static void insertSort(int[] arr){
  13.         for (int i = 0; i < arr.length; i++) {
  15.             int insertVal = arr[i];//定义有序表的最后一个元素
  16.             int insertIndex = i-1;//定义有序表最后一个元素的下标
  17.             //最后一个元素依次往前比较
  18.             while (insertIndex >= 0 && insertVal < arr[insertIndex]){
  19.                 //将比它大的元素往后移
  20.                 arr[insertIndex+1] = arr[insertIndex];
  21.                 //下标递减
  22.                 insertIndex -= 1;
  23.             }
  24.             //退出循环，找到了位置，在后一个位置插入
  25.             arr[insertIndex+1] = insertVal;
  27.             System.out.println("第"+(i+1)+"轮插入："+ Arrays.toString(arr));
  29.         }
  30.     }
  32. }

3、运行结果

图片.png

4、测试插入排序

测试排序对80000个随机数进行排序，仅仅不到1s
图片.png
测试源码

  1. package com.study.sort;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. public class InsertSort {
  8.     public static void main(String[] args) {
  9.         /*int[] arr = {50,40,101,34,99,1};
  10.         insertSort(arr);*/
  12.         int[] arr = new int[80000];
  13.         Random random = new Random();
  14.         for (int i = 0; i < 80000; i++) {
  15.             arr[i] = random.nextInt(800000000);
  16.         }
  18.         long l1 = System.currentTimeMillis();
  20.         insertSort(arr);
  22.         long l2 = System.currentTimeMillis();
  24.         System.out.println("插入排序对"+arr.length+"个数据排序所花费的时间为："+(l2-l1)+"ms");
  25.     }
  27.     public static void insertSort(int[] arr){
  28.         for (int i = 0; i < arr.length; i++) {
  30.             int insertVal = arr[i];//定义有序表的最后一个元素
  31.             int insertIndex = i-1;//定义有序表最后一个元素的下标
  32.             //最后一个元素依次往前比较
  33.             while (insertIndex >= 0 && insertVal < arr[insertIndex]){
  34.                 //将比它大的元素往后移
  35.                 arr[insertIndex+1] = arr[insertIndex];
  36.                 //下标递减
  37.                 insertIndex -= 1;
  38.             }
  39.             //退出循环，找到了位置，在后一个位置插入
  40.             arr[insertIndex+1] = insertVal;
  42.             //System.out.println("第"+(i+1)+"轮插入："+ Arrays.toString(arr));
  44.         }
  45.     }
  47. }