java算法-插入排序
一、原理
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
二、代码
public static int[] insertSort(int[] arr){if (arr == null || arr.length==1){return null;}for (int i=1;i<arr.length;i++){int insertVal = arr[i];//需要插入的值//9,2,1,5,3,8,10,11,6,4int index = i-1;//前一个元素的下标//当前下标索引大于等于0且要插入的值小于它前一个元素的值while(index >= 0 && insertVal < arr[index]){arr[index+1] = arr[index];index--;}arr[index+1] = insertVal;}return arr;}
插入排序的时间复杂度：
在最好的情况下（元素已经排好顺序）：那么只需要循环 n-1 次就可以了，时间复杂度 O（n）
在最差的情况下 （元素是逆序的）：要循环调整次数：[ n * (n-1) ] / 2 ，时间复杂度为 O（n ^ 2）
平均时间复杂度为：O（n ^ 2）
插入排序的空间复杂度：O(1)