1 基本原理
插入排序就是将未排序的数据插入到已经排序数据的适当位置，插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
2 时间复杂度
O(n^2)
插入排序的性能受原始数据的影响较大，如果是基本有序的数据，插入排序就会很块，正是因为如此，在很多高级排序算法中，当数据缩减到比较小的时候，往往采用插入排序进行优化，这也证明了时间复杂度为O(n^2)的排序算法还是很有实用价值的
3 代码实现
public class InsertionSort {
public static void sort(
int[] arr) {
for (
int i =
1; i < arr.length; i++) {
for (
int j = i; j >
0 && arr[j] < arr[j -
1]; j--) {
swap(arr, j, j -
1);
}
}
}
private static void swap(
int[] arr,
int i,
int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] arr = {
10,
9,
8,
7,
6,
5,
4,
3,
2,
1 };
InsertionSort.sort(arr);
for (
int i =
0; i < arr.length; i++) {
System.
out.print(arr[i]);
System.
out.print(
' ');
}
System.
out.println();
}
}
