插入排序(Insert Sort), java版

插入排序(Insert Sort), java版.

java 的库很丰富，为了复习下数据结构与算法，博客一下，方便自己以后查看，现在先为 插入排序写个代码。

插入排序原理：前面的都是有序的(x1,x2...xk)，在添加一个数据e时，从最后一个到最一个比较(从xk到x1)，直到找到合适的位置（比如，从小到大排序——直到第一个比e小）。
时间复杂度：平均O(n2)，最坏情况O(n2)。

下面来看下代码：

1. package?com.chenlb.sort;??
2. ??
3. import?java.util.Arrays;??
4. ??
5. public?class?InsertSort?{??
6. ??
7. ????public?static?int[]?sort(int[]?datas)?{??
8. ????????for(int?i=1;?i<datas.length;?i++)?{??
9. ????????????for(int?j=i-1;?j>=0;?j--)?{??
10. ????????????????if(datas[j]?>?datas[j+1])?{??
11. ????????????????????SortUtil.swap(datas,?j,?j+1);???//交换??
12. ????????????????}??
13. ????????????}??
14. ????????}??
15. ????????return?datas;??
16. ????}??
17. ??
18. ????public?static?void?main(String[]?args)?{??
19. ????????int[]?datas?=?{5,1,3,4,9,2,7,6,5};??
20. ????????sort(datas);??
21. ????????System.out.println(Arrays.toString(datas));??
22. ??
23. ????????datas?=?SortUtil.randomDates(10);??
24. ????????sort(datas);??
25. ????????System.out.println(Arrays.toString(datas));??
26. ????}??
27. ??
28. }??

运行结果：

1. [1,?2,?3,?4,?5,?5,?6,?7,?9]??
2. [49,?97,?200,?262,?356,?368,?618,?624,?682,?925] ?

?