排序算法-插入排序
2018-02-27 本文已影响11人
石头怪
插入排序
在一组数据中,将当前数据与之前已经排好序的数据从后往前进行大小比较,后将该数据插入合适的位置,直到最后完成最终排序。
代码实现
插入排序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