插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序的序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描的过程中，需要反复把已排序的元素逐步向后移动，为最新元素提供插入空间。
算法步骤：
初始化一个数组。
|
(1) 对于第1个元素，因为没有比较，直接将其作为有序的序列。
|
(2) 从数组中获取下一个元素，在已经排序的元素序列中从后向前扫描，并进行判断。若排序序列的元素大于新元素，则将该元素移动下一位置。直到找到已排序的元素小于或者等于新元素的位置。
(3) 重复此(2)步骤
|
算法实现：
public class InsertSort {
public static void main(String[] args) { int arr[]= {56,20,38,75,26,91,16}; System.out.println("排序前："+Arrays.toString(arr)); sort(arr); System.out.println("排序后："+Arrays.toString(arr)); } public static void sort(int arr[]) { int temp,j; for(int i=1;i<arr.length;i++) { temp=arr[i]; for(j=i-1;j>=0 && arr[j]>temp;j--) { arr[j+1]=arr[j]; } arr[j+1]=temp; } } } |
排序前：[56, 20, 38, 75, 26, 91, 16] 排序后：[16, 20, 26, 38, 56, 75, 91] |