插入排序属于稳定排序，他的时间复杂度为O(n^2)
思路和过程：把n个待排序的元素分为有序表和无序表，开始前有序表只有一个元素即n个元素的中的第一个，无序表中有n-1个元素，开始排序时从无序表中取出当前第一个元素，和有序表中相比较，将他插入到合适位置，当无序表中的元素提取完，排序即可完成
优化：当有的数字已经在他的正确位置时，我们在进行赋值就会影响速度，所以我们只有在他需要进行移动时赋值即可
import java.lang.reflect.Array; import java.util.Arrays; public class InsertSort { public static void main(String[] args) { int[] arr = {101, 34, 199, 1}; insertSort(arr); } public static void insertSort(int[] arr) { int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { insertVal = arr[i]; insertIndex = i - 1; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //优化 if (insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } } } }
原文：https://www.cnblogs.com/bingbug/p/12114508.html