算法基本思想：

插入排序（Insertion Sort）算法通過對未排序的數(shù)據(jù)執(zhí)行逐個(gè)插入至合適的位置而完成排序工作。

示意圖

排序流程：

1. 首先對數(shù)組的前兩個(gè)數(shù)據(jù)進(jìn)行從小到大排序
2. 然后將第三個(gè)數(shù)據(jù)與前面排好的數(shù)據(jù)進(jìn)行比較，把第三個(gè)數(shù)插入合適的位置
3. 然后將第四個(gè)數(shù)據(jù)插入到前三個(gè)數(shù)據(jù)中
4. 重復(fù)此步驟，直到最后一個(gè)數(shù)插入合適的位置為止，到此排序完成

代碼實(shí)現(xiàn)

import java.util.Arrays;

public class InsertionSort {
    public static void sort(int[] arr) {
        int len = arr.length;
        int tmp;//要插入的數(shù)據(jù)
        int istIndex;//插入位置索引
        System.out.println("原始順序： " + Arrays.toString(arr));
        for (int i = 1; i < len; i++) {
            if (arr[i] < arr[i - 1]) {
                tmp = arr[i];
                istIndex = i;
                while (istIndex > 0 && arr[istIndex-1] > tmp) {
                    //插入位置往前移，尋找合適位置
                    arr[istIndex] = arr[istIndex - 1];
                    istIndex--;
                }
                arr[istIndex] = tmp;
            }
            System.out.println("第" + i + "趟排序：" + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        //初始化數(shù)組
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * (100 + 1));
        }
        InsertionSort.sort(arr);
    }
}