承接上文选择排序、冒泡排序、异或运算
上文题目2代码
定义一个eor变量 定义一个整型数组int[] 用eor变量异或数组中的每一个元素 那么eor就变成了a^b 又因为知道了该数组中有2种数出现了奇数次 所以a != b 所有eor != 0 意味着eor必有一个位置上是1 选最右侧的1 int rightOne = eor & (~eor + 1) 这一行的代码表示把某一个不等于0的数最右侧的1提取出来
一个数与上这个数取反加1就是把这个数最右侧的1取出来了 onlyOne就是eor' 遍历数组，数组中的每个数和rightOne做与运算结果为0或1的 才让eor'与这个数做与运算 总之那个位置上等于1或等于0的才异或 一个数字和0000000100异或不等于0 就是等于1 那么这个数字的从右往左的第三位必须是1才不等于0 onlyOne是a或者b 另一个就是eor异或上onlyOne的结果
插入排序
定义一个数组 3,2,5,4,2,3,3, 下标是0,1,2,3,4,5,6
0～0 范围是有序的 只有一个数 0~1排序 如果当前位置所在的数比左边小就交换 所以3，2交换
2这个数来到了0位置 再往前看 没有数了 可以停了 此时也做到了0～1上有序了
画线部分表示已经做到有序了 接下来想做到0～2范围有序 所以从2开始往前看 5的前一个数是3 不需要交换 此时就做到了0～2有序了
当前这个数就来到了4这个位置 再往前看 4>3 停 此时就已经做到了0～3有序了 依此类推 就像打扑克 抓了一张新牌 旧牌从右往左划到适当的位置插入进去
时间复杂度
数据状况不同会导致时间复杂度不一样
选择排序和插入排序的数据状况不影响时间复杂度
这种情况只需要往前看看 不需要排序 时间复杂度是O(N)级别 时间复杂度按最差情况来估计你的算法表现 所以说插入排序是O(N^2)的算法
插入排序代码
