插入排序
在一组数据中，将当前数据与之前已经排好序的数据从后往前进行大小比较，后将该数据插入合适的位置，直到最后完成最终排序。
代码实现
插入排序C++.png
结果
插入排序结果.png
具体过程
仍然使用Android实现整个排序过程。
插入排序动画显示.gif
- 第一趟 :从第二个数字30开始，与之前数字42比较，发现30<42,将30插入42之前，（从实现上来说，是与42交互位置）
-第二趟：68与42比较，再与30比较，没有变化，不交换位置
........
直到最后从小到大排完。
总结
从排序上来看，如果所有的数据完全逆序，则所需要的排序次数为O(N^2)；
如果说，数据已经排好，则所需要的次数为O(N)；
这样看来，当数据中数据有大量重复数据，或者已经排好序的数据，插入排序的时间复杂度将不断降低。
另附java代码实现：
插入排序java实现.png
插入排序的改进方法：
减少赋值交换操作，节省更多时间。
大体思路：依次取出数据值，copy一份当前选择的数据，依次与前面已经排好序的数据进行比较，直到选到合适的位置进行交换操作。
具体实现：
插入排序改进-java.png
网友评论