三大基本排序算法之一，插入排序（Insertion Sort）。
插入排序就是把一个数插入一个已排好的序列中。
前提：
排序结果为从小到大。
插入排序的步骤：
1、一个序列，把第一个数当成一个已排好的序列。
2、从待排序的序列中取第一个数，与已排序序列中的数从后向前挨个比较大小，
3、若是待排序的数比已排序的数小，把已排序的数在序列中向后移一个位置。
4、重复第3步，继续比较下一个已排序的数与待排序的数。
5、把待排序的数插入到空出的位置上。
6、重复第2~5步，直到待排序序列为空。
代码实现：
1. public void sort(){ 2. 3. int[] a = {9,2,4,5,7,6,8,3,1,0}; 4. 5. System.out.println("first:"+Arrays.toString(a)); 6. 7. for(int i=1,num=a.length; i<num; i++) 8. { 9. int temp = a[i]; //记录待排序的数值 10. int positon = 1; //记录待排序的数值应该插入的位置 11. 12. for(int j = i-1;j>=0;j--) 13. { 14. //如果待排序数比已排序的数小，已排序数向后移一位。 15. if(temp < a[j]){ 16. a[j+1] = a[j]; //位置后移一个 17. positon = j; //把空出来的位置拿到 18. 19. } 20. } 21. a[positon] = temp; //把待排序的数据插入到空出的位置上 22. 23. } 24. System.out.println("second:"+ Arrays.toString(a)); 25. 26. }
在网上找到一个形象的图形很有意思：
参考文章： http://bubkoo.com/2014/01/14/sort-algorithm/insertion-sort/
总结：
插入排序在最后一个数排完之前，已排序好的序列是不固定的。
又一次学习算法，这次收获很大。要刻意练习，才能达到优秀的程度。
