插入排序之我的理解

最近复习了下插入排序,确切的说是直接插入排序，因为插入排序之中还有个高级算法shell排序，高级的暂不讨论。

直接插入排序的主要思路不难理解，百度了下，有个大神的回复就很清晰易懂：

 

From 百度知友ch_cityhunter：

1 5 7 3 1 6
  把表分成两部分，前半部分已排序，后半部分未排序，我用|分开初始为 5 | 1 7 3 1 6
  一次插入排序，把第一个1插入前边已排序部分，得
1 5 | 7 3 1 6
  后边依次是
1 5 7 | 3 1 6
1 3 5 7 | 1 6
1 1 3 5 7 | 6
1 1 3 5 6 7 |

 

这个思路很容易理解吧，但代码实现却不是那么简单，平时习惯for循环，来个while，还真有点接受不了，感觉while太执着了，只要心中还有残念，就一直“不死不休”的坚持下去。

来个例子说明：

 

Index	0	1	2	3	4	5	6	7	8	9
Value	72	6	57	88	60	42	83	73	48	85

 

第一步, 从数组的第二个数字(index=1)开始遍历：

 

拿出6放到一边(设置为temp)，判断左边第一个元素值(index=0)是否大于它，72>6， 则将72放置到6的位置。

 

Index	0	1	2	3	4	5	6	7	8	9
Value	72	72	57	88	60	42	83	73	48	85

 

索引前移，index = -1，break跳出。将temp值放入index+1， 就是0 这个位置。

Index	0	1	2	3	4	5	6	7	8	9
Value	6	72	57	88	60	42	83	73	48	85

 

第二步，拿出index=2的元素temp=57，向左遍历。取index=1的元素与它比较，72>57，则72放置在57的位置：

 

Index	0	1	2	3	4	5	6	7	8	9
Value	6	72	72	88	60	42	83	73	48	85

 

继续索引前移，index=0，6<57,遇到了比temp小的数值，循环停止。将temp放置到当前index+1的位置：

 

Index	0	1	2	3	4	5	6	7	8	9
Value	6	57	72	88	60	42	83	73	48	85

 

剩下的原理一样。取出当前循环中,索引指向的数值放入temp中, 向左迭代，遇到比自己大的数则大数右移, 遇到比自己小的数, 则temp入坑. 若遇不到小数,也就是说当前temp是最小数,此时的index=-1, 则break结束迭代. 代码实现如下:

 

public class MyInsertSort {
	/**
	 * insert sort
	 * 
	 * @param a
	 */
	public static void insertSort(int[] a) {
		for (int j = 1; j < a.length; j++) {
			int tmp = a[j];
			int i = j - 1;
			while (tmp < a[i]) {
				a[i + 1] = a[i];
				i--;
				if (i == -1)
					break;
			}
			a[i + 1] = tmp;
		}
	}

	/**
	 * main()测试方法
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
		insertSort(a);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}
}