数据结构与算法|数据结构与算法——插入排序算法|数据结构

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

文章图片

小结：
1：大循环次数数组大小-1 次
2：每次大循环后有序数组个数加一，无序数组个数减一
【数据结构与算法|数据结构与算法——插入排序】3：大循环就是把后面无序部分拿出与有序对比大小，然后插入有序数组

import java.text.SimpleDateFormat; import java.util.Arrays; import java.util.Date; public class InsertSort { public static void main(String[] args) { int []arr = {101,34,119,1}; int arr2[] = new int[80000]; for (int i=0; i<80000; i++){ arr2[i]=(int)(Math.random()*800000); }Date date1 = new Date(); SimpleDateFormat format = new SimpleDateFormat("yyy-MM-dd HH:mm:ss"); String d1 = format.format(date1); System.out.println("排序前："+d1); insertSort(arr2); Date date2 = new Date(); String d2 = format.format(date2); System.out.println("排序后："+d2); }public static int[] insertSort(int[] arr){ for (int i = 0; i= 0 && insertValue < arr[insertIndex]){ arr[insertIndex+1] =arr[insertIndex]; insertIndex--; } //优化 if(insertIndex != i){ arr[insertIndex+1]=insertValue; } } return arr; } }

说明：插入排序时间复杂度为n^2
测试排序80000条数据时间：1秒