大家应该都打过扑克牌，插入排序和整理扑克牌非常类似，将每一张牌插到其他已经有序的牌中的适当的位置（好在扑克牌比较少，在不考虑红黑方草的前提下顺序也就是从A到K）。
对于这类排序，就有两种基本的操作，1、比较操作 2、交换操作
插入排序算法有种递归的思想在里面，它有N-1趟排序组成。初识时，只考虑数组下标的0出的元素，只有一个元素，显然是有序的（和我们抓到第一张扑克牌一样，放在哪里都是有顺序的）。
然后第一个对下标1出的元素进行排序，保证数组[0，1]上的元素有序；
第二趟对下标2出的元素进行排序，保证数组[0,2]上的元素有序；
...
...
第N-1趟对N-1出的元素进行排序，保证数组[0，N-1]上的元素有序，也就是整个数组有序了。
它的递归思想就体现在：当对位置i处的元素进行排序时，[0,i-1]上的元素一定是已经有序了/
悟：整个过程和抓牌是一样的，在抓到第i 张扑克牌时，一定要保证前面的扑克牌是有序的。否则插在哪都是无序。落实到代码与我们实际结合，这里存在两种写法，个人总结为1、两两比较、交换位置，然后重复上述的动作。2、持续比较，找到合适的位置，然后插入数据（正常我们插排应该是这种操作）。
方法1的插入操作代码如下：
package insertionSort
//插入排序算法
复杂度分析
1、插入排序的时间复杂度，就是判断比较次数有多少，这个次数和待排序的切片初始顺序有关，当代待排序的切片是正序是，则嵌套的for循环不会被执行，此时复杂度为O(n);当待排序的切片为逆序时，比较次数为最多，对于下标为i的元素，需要比较i-1次。总的比较为1+2+3+...+i-1次，因此时间复杂度为O(n^2)
2、可以看出，算法中只用到了临时变量temp，因此空间复杂度为O(1)。
上面的就是每次对比两个数，然后颠倒下位置，然后再继续向下比较。我们再试着用方法2实现下。
和第一种方法没有什么本质的区别，只是减少了temp插入到数组的此时，直到找到位置之后插入一次。
网友评论