算法基本思想：
插入排序（Insertion Sort）算法通過對(duì)未排序的數(shù)據(jù)執(zhí)行逐個(gè)插入至合適的位置而完成排序工作。
示意圖
排序流程：
- 首先對(duì)數(shù)組的前兩個(gè)數(shù)據(jù)進(jìn)行從小到大排序
- 然后將第三個(gè)數(shù)據(jù)與前面排好的數(shù)據(jù)進(jìn)行比較择懂，把第三個(gè)數(shù)插入合適的位置
- 然后將第四個(gè)數(shù)據(jù)插入到前三個(gè)數(shù)據(jù)中
- 重復(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);
}
}
