Java学习之路——插入排序

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

26

插入排序

排序思想:每步将一个待排序的记录,按其数组下标大小插入到前面已经排序的子序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
  排序举例: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