插入排序
一、分类
1、直接插入排序
2、希尔插入排序
1、直接插入排序
A.含义
讲一个记录插入到已经排序好的有序列表当中。
B.步骤
a.sorted数组的第0个位置没有放入数据
b.从sorted第二个数据开始处理:如果该数据比前面的数据小.说明该数据需要往前面移动。
（1）首先将该数据备份到 sorted的0号位置作为"哨兵"
（2）然后将该数据的前面那个数据往后移动
（3）然后往前搜索，找插入的位置
（4）找到插入的位置之后，第0位置的那个数据插入到对应的位置。
直接插入排序.PNG
2、希尔排序（缩小增量排序 diminishing increment sort）
A.含义
先将整个等待排序的代码分割成为若干的子序列，分别进行直接插入排序，等待整个序列中记录基本有序的时候，再对全体进行一次直接插入排序
B.插入排序代码
main()方法的写法
public static void main(String[] args) {
Random r = new Random();
int size = 10;
int[] array = new int[size];
//排序前,赋值并且打印
System.out.println("排序前:");
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(100);
System.out.print(array[i]+" ");
}
System.out.println();
//调用排序方法
insertSort(array);
//排序后,打印输出结果
System.out.println("排序后:");
for (int i = 1; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
排序方法的写法
//直接插入排序的方法
public static void insertSort(int[] arr){
int len = arr.length;
for (int i = 2; i < len; i++) {
if(arr[i]<arr[i-1]){
arr[0] = arr[i];
arr[i] = arr[i-1];
int insertPosition = 0;
for (int j = i-2; j >=0; j--) {
if (arr[j]>arr[0]){
arr[j+1] = arr[j];
}else{
insertPosition = j+1;
break;
}
}
arr[insertPosition] = arr[0];
}
}
}
运行结果
排序前:
2 68 46 58 81 61 18 27 54 43
排序后:
18 27 43 46 54 58 61 68 81 