插入排序
排序思想:每步将一个待排序的记录,按其数组下标大小插入到前面已经排序的子序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
排序举例:int a[]= {1,7,2,9,8,4},默认第一个数组元素以排好序,选定第二个开始插入。
第一次排序:选定a[2] = 7排序。
1<7,不交换位置
排序结果:1 7 2 9 8 4
第二次排序:选定a[3] = 2排序。
7>2,交换位置
1<2,不交换位置
排序结果:1 2 7 9 8 4
第三次排序:选定a[4] = 9排序。
7<9,不交换位置
2<9,不交换位置
1<9,不交换位置
排序结果:1 2 7 9 8 4
第四次排序:选定a[5] = 8排序。
9>8,交换位置
7<8,不交换位置
2<8,不交换位置
1<8,不交换位置
排序结果:1 2 7 8 9 4
第五次排序:选定a[6] = 4排序。
9>4,交换位置
8>4,交换位置
7>4,交换位置
2<4,不交换位置
1<4,不交换位置
排序结果:1 2 7 8 9 4
代码实现:
public static int[] insertSort(int[] data) {int temp; //临时变量int j; //定位比较的数组元素下标for (int i = 1; i < data.length; i++) {//默认第一个元素以排好序,从第二个元素开始扫描,共扫描length-1次temp = data[i];j = i-1;//将data[i]与他的前一位data[i-1]比较while(j>=0 && temp










