插入排序
代码语言：javascript复制public static void insertSort(int[] arr, int l, int r){
for(int i = l 1; i <= r; i ){
int tmp = arr[i];
int j;
// 提前终止，当元素全部有序，可退化成O(n)
for(j = i ; j > l && arr[j - 1] > tmp; j--){
arr[j] = arr[j - 1];
}
// 减少交换
arr[j] = tmp;
}
}
public static void main(String[] args) {
int[] arr = {2,4,5,3,1,8,1,4,3};
insertSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
