排序算法-插入排序

插入排序

在一组数据中，将当前数据与之前已经排好序的数据从后往前进行大小比较，后将该数据插入合适的位置，直到最后完成最终排序。

代码实现

插入排序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