插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
算法图示：
算法基本性能
| 排序方法 | 平均时间复杂度情况 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
Java代码
package com.sort;
import java.util.Random;
public class Main {
// 从小到大
private static void sort(int[] array) {
if (array.length <= 1) {
return;
}
for (int i = 1; i < array.length; i++) {
/**
* 因为0~i-1为有序的，如果i位置的大于i-1位置的，说明0~i也是有序的，
* 反之需要在0~i-1直接找出i位置的元素的正确位置插入
*/
if (array[i] < array[i - 1]) {
/**
* 先保存i位置元素
*/
int temp = array[i];
int j = i - 1;
/**
* 从i-1开始向前查找，一直到找到比i位置元素小的位置，然后插入
*/
for (; j >= 0 && array[j] > temp; j--) {
/**
* 没有找到，那么将此位置的元素后移一位，腾出位置
*/
array[j + 1] = array[j];
}
/**
* 将i位置元素放在腾出的位置上面
*/
array[j + 1] = temp;
}
}
}
/**
* 获取指定长度的随机数组
*/
public static int[] getRandomArray(int n) {
int[] array = new int[n];
Random random = new Random();
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(500);
}
return array;
}
/**
* 打印指定数组
*/
public static void outputArray(int[] array) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println("");
}
public static void main(String[] args) {
int[] array = getRandomArray(10);
outputArray(array);
sort(array);
outputArray(array);
}
}