乐趣区

关于算法:算法学习笔记-day1-位运算选择冒泡排序

jiezi

视频源连贯

抉择排序

思路：

  1. 从数组索引 0 开始，找比以后值更小的值，找到即为最小值
  2. 找到最小值后替换以后索引值以及最小值所在索引值
  3. 反复遍历
    源代码：

冒泡排序

思路:

  1. 从数组索引 0 开始，只有以后值比他下一位值大，替换两者程序。
  2. 反复遍历
    源代码：

位运算

  1. a ^ b 雷同为 0 不同为 1
  2. 位运算满足交换律和结合律 即：a^b = b^a; (a^b)^c = a^(b^c)
  3. 0 ^ N = N; N^N = 0;
  4. 位运算能够了解为二进制的不进位相加
    比方: 101 ^ 011 = 110; 通过这个，能够进一步了解为什么满足交换律 因为无论多少个数字异或，那么雷同地位上是 1 还是 0 齐全取决于 1 和 0 的数量，与程序无关

所以反过来看冒泡排序中的 swap，原理如下：

但值得注意的是，其中 i 和 j 不能是雷同值，雷同值相当于本人和本人异或 那么会清 0 导致计算结果不精确。

  1. 提取一个数最右的 1:int rightOne = eor & (~eor +1); 原理如下：
    思路: 本人与本人取反加 1;

原题：数组中有两个数是奇数个，其余数为偶数个，找出这两个数：

插入排序

思路:

  1. 从数组索引 1 开始，向前比拟找到适合的地位插入

源代码：

相较于抉择和冒泡，插入排序最差是 On^2 最好是 On 依据数据状况来定，绝对性能较好

二分法

常见问题:

  1. 有序数组 找某个数是否存在
  2. 有序数组 找大于某个数最左侧的地位
  3. 部分最小值
    一个 arr 中 任意两个元素相邻数肯定不相等，找任意一个部分最小值，部分最小为 i 比 i -1, 比 i +1 都小。要求工夫复杂度好于 On 最好用二分

思路:

解释：首先判断 0 和 n 是不是部分最小 不是的话那么 0 -1 肯定是大小向下的趋势，n 到 n - 1 肯定是向下的。那么 1 到 n - 1 之间肯定有个最小值。
所以这个时候你找 m 如果不是的话 m 到 m - 1 之间肯定是向下的那么 m - 1 到 1 之间肯定存在最小值

生成 0 - n 的随机数

Math.random() => [0 - 1) 所有的小数
Math.random() * N => [0, N) 所有小数
parseInt(Math.random () *N)=> [0, N-1]所有整数 等概率返回

解决理论问题的思路：1. 数据非凡能够优化，2 问题非凡能够优化

退出移动版