算法描述
- 从第二个元素开始，依次插入其前有序数列（可以提前终止内循环的原因）的合适位置；
时间复杂度
- 最好情况，O(N)，数组近乎有序的情况下；
- 最坏情况，O(N^2)；
- 平均情况，O(N^2)；
算法实现
- 外层循环控制遍历的范围，一点点变大；
- 内层循环在范围里比较，和前面的元素比；
- 注意插入排序的内层循环的时候，是有机会提前终止的（比之前的元素大），不必将内层循环完整走一遍；
- 注意swap(Object[] arr, int j, int i) 中，数组的入参是用 Object[] 而不是 Compareble[]；
import util.SortTestHelper;
public class InsertionSort {
private InsertionSort(){}
public static void sort(Comparable[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j].compareTo(arr[j - 1]) < 0) {
swap(arr, j, j - 1);
} else {
break;
}
}
}
}
private static void swap(Object[] arr, int j, int i) {
Object temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public static void main(String[] args) {
int N = 10000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("_02.sortingbaisc._05.InsertionSort", arr);
}
}
输出：
InsertionSort : 156ms
