1. 认识复杂度和简单排序算法

1. 认识复杂度和简单排序算法

常数时间的操作，一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
例子:

int a = arr[i];
1

时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

1. 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：

1. 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。
2. 然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
3. 以此类推，直到全部待排序的数据元素的个数为零。

选择排序是不稳定的排序方法。时间复杂度O(n^2)， 空间复杂度O(1)。
例如给定一组数据，[4, 2, 3, 6, 5]其排序过程如以下所示
第一次: [2, 4, 3, 6, 5]
第二次: [2, 3, 4, 6, 5]
第三次: [2, 3, 4, 6, 5]
第四次: [2, 3, 4, 5, 6]
第五次: [2, 3, 4, 5, 6]

以下是@五分钟学算法大佬的动画，侵删。

java代码实现:

package paixu;
import java.util.Arrays;
public class Code01_SelectionSort {
    public static void main(String[] args) {
        int[] arr = {4, 2, 3, 6, 5};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2. 冒泡排序

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序是稳定的排序方法。时间复杂度O(n^2)， 空间复杂度O(1)。

java代码:

package paixu;

import java.util.Arrays;

public class Code02_BubbleSort {
    public static void main(String[] args) {
        int[] arr = {6,4,1,2,9,3,7,8,10,5};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            boolean flag = true;
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }

    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
//        int tmp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = tmp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

3. 异或运算

异或运算资源来自 https://blog.csdn.net/weixin_43614026/article/details/104341932

如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以 异或常被认作不进位加法。（来源于搜狗百科）

例如，计算 1011101^1000011:

异或性质与扩展
（用不进位相加较好理解）

• 0 ^ N = N
• N ^ N = 0

异或运算满足交换律和结合律

• c =a ^ b =b ^ a
• c =（ a ^ b ）^ c = a ^ ( b ^ c )

不用额外变量交换两个数：

• 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这个数？
  例如，该数组为 a[]={1, 2, 2, 3, 3}
  将所有的数全部异或运算，运算结果就是出现了奇数次的数。
• 一个数组中有两种出现了奇数次，其他数都出现了偶数次，怎么找到这两个数？
  例如，该数组为a[]={1,2,4,4,5,5}，分析步骤如下:

1. 让该数组中所有的数字做异或运算，那么设结果 eor == a ^ b != 0 ;
2. 因为eor 不为 0 ，则可以假设 a 与 b在某位上，比如在第三位上，a第三位是1，则b的第三位为0；
3. 在其余的出现偶数次的数字中，找出所有在第三位为1的数；
4. 用变量 eor’ 与这个数组中所有第三位为1的数做异或运算 ，则 eor’ 最终的答案为a，因为所有第三位为1的数字，除了a，其余为偶数 个，异或运算后为0。(因为除了a 与 b ，其余数字的个数都为偶数个，那么可以确定第三位为1的和第三位为0的个数都为偶数个。因为 eor = a ^ b,且其余偶数运算之后结果为0，如果第三位为1的数字个数为奇数，那么第三位为0的数字个数也为奇数，那么将他们全部进行异或运算后，第三位数字为1，不为0，与实际不符。)
5. 再用eor与eor’做异或运算，即a ^ b ^ a = b;

以下给出该题解的代码：首先了解如何取到该数最右端的1，就是该数取反+1再&该数 （核心：int rightOne = eor & ( ~ eor + 1 ); ）

java代码:

package paixu.class01;

public class Code07_EvenTimesOddTimes {
    public static void main(String[] args) {
        int[] arr = {1,2,4,4,5,5};
        printOddTimesNum2(arr);
    }


    public static void printOddTimesNum2(int[] arr) {
        int eor = 0, onlyOne = 0;
        for (int curNum : arr) {
            eor ^= curNum;
        }
        //eor = a ^ b
        //eor != 0
        //eor 必然有一个位置上是 1
        int rightOne = eor & (~eor + 1);    //提取出最右的1
        System.out.println("右边第" + rightOne + "位是0的有以下这些数");
        for (int cur : arr) {
            if ((cur & rightOne) == 0) {
                System.out.println(cur);
                onlyOne ^= cur;
            }
        }
        System.out.println("这两个数分别是:\t" + onlyOne + "\t" + (onlyOne ^ eor));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

4. 插入排序

插入排序的原理：
一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
选择排序的基本思想是：

将未排序的元素一个一个地插入到有序的集合中，插入时把所有有序集合从后向前扫一遍，找到合适的位置插入。

插入排序是稳定的排序方法。时间复杂度O(n^2)， 空间复杂度O(1)。
下图来源 https://blog.csdn.net/hcz666/article/details/126488359。插入排序的过程如下：

java代码:

package paixu.class01;

import java.util.Arrays;

public class Code03_InsertSort {
    public static void main(String[] args) {
        int[] arr = {9,7,8,2,5,1,3,6,4};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //0~0 有序
        //0~i 想有序
        for (int i = 1; i < arr.length; i++) {
            // 0~i 做到有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i]^ arr[j];
        arr[j] = arr[i]^ arr[j];
        arr[i] = arr[i]^ arr[j];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5. 二分法的详解与扩展

• 在一个有序数组中，找某个数是否存在。时间复杂度O(logN)
  java代码:

package paixu.class01;

public class Code04_BSExist {
    public static void main(String[] args) {
        int[] sortedArr = {1,2,3,4,5,6,7,8,9};
        System.out.println(exist(sortedArr, 5));
    }
    public static boolean exist(int[] sortedArr, int num) {
        int L = 0;
        int R = sortedArr.length - 1;
        while (L <= R) {
            int mid = L + ((R-L) >> 1);
            if (sortedArr[mid] == num) {
                System.out.println("目标数下标:" + mid);
                return true;
            }
            if (sortedArr[mid] > num) {
                R = mid - 1;
            }else {
                L = mid + 1;
            }
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 在一个有序数组中， 找>=某个数最左侧的位置

java代码

package paixu.class01;
public class Code05_BSNearLeft {
    public static void main(String[] args) {
        int[] arr = {1,2,3,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6};
        System.out.println("最左边的值为:" + nearestIndex(arr, 6));
    }
    // 在arr上，找满足>=value的最左位置
    public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while (L <= R) {
            int mid = L + ((R-L) >> 1);
            if (arr[mid] >= value) {
                R = mid - 1;
                index = mid;
            }else {
                L = mid + 1;
            }
        }
        return index;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 局部最小值问题
  题目描述
  局部最小值定义：

1. 最左边边界处，如果最左边的数小于左边第二个数，则最左边为局部最小值。
2. 最右边边界处，如果最右边的数小于右边第二个数，则最右边为局部最小值。
3. 中间处，如果一个数小于它两边的数，则这个数就是局部最小值。

说白了，就是二维坐标系中的任意一个最低点，都是局部最小值。现在，有一个数组，相邻的两个数不相等，请求出一个数组中的一个局部最小值。
算法思路

1. 首先，先观察最左边的第一个和第二个数，判断是否是局部最小值。
2. 然后，再观察最右边第一个和第二个数，判断是否是局部最小值。
3. 如果最左边和最右边有一个是局部最小值，则此题结束。
4. 否则，说明一个什么问题？说明左边的曲线是向下递减的，右边的曲线也是向上递增的，对吧？那么，中间是必定有局部最小值的，这是在高数最大值最小值中有类似的定义，对吧？
5. 然后，直接用二分法，选取中间的数，判断其是不是局部最小值？如果不是的话，观察他左右趋势，假如，它左边一个数比他小，说明什么？说明它左边是递增的，而此时最左边的递减的，通过上面分析4的判断，说明它左边存在局部最小值，然后，再其左边区间，再次二分法，直到找到局部最小值。

总结:
这题代码其实就是二分查找。关键是此题的思路，这是重点，此题说明了，二分查找并不一定只能求解有序数组中的某个数。在一些能够直接排除掉一半区间的例子中，也同样可以使用二分法来解决，将时间复杂度直接降低到O(logn)。
就比如此题，可以根据一个区间两边的递增递减性，来判断区间内是否有局部最小值，那么，就可以直接用二分法从中间划分，然后根据判断条件，可以直接排除掉一半区间。

java代码:

package paixu.class01;

public class Code09_FindOneLessValueIndex {
    public static void main(String[] args) {
        int[] arr = { 6, 5, 3, 4, 6, 7, 8 };
        int[] arr1 = {1,2,3,4,5,6,7,8};
        int[] arr2 = {2,1,3,4,5,6,8,7};
        System.out.println("(中间情况)arr局部最小索引为:" + getLessIndex(arr) + "\t值为" + arr[getLessIndex(arr)]);
        System.out.println("(左边情况)arr1局部最小索引为:" + getLessIndex(arr1) + "\t值为" + arr1[getLessIndex(arr1)]);
        System.out.println("(右边情况)arr2局部最小索引为:" + getLessIndex(arr2) + "\t值为" + arr2[getLessIndex(arr2)]);
    }
    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        //1.先观察最左边的第一个和第二个数，判断是否是局部最小值
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        //2.再观察最右边第一个和第二个数，判断是否是局部最小值
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        //3.局部最小值在中间
        int L = 1;
        int R = arr.length - 2;
        while (L <= R) {
            int mid = L + ((R-L) >> 1);
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid+1]) {
                return mid;
            }
            if (arr[mid] < arr[mid+1]) {
                R = mid - 1;
            }else {
                L = mid + 1;
            }
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

6. 对数器的概率和使用

1. 有一个你想要测的方法a
2. 实现复杂度不好但是容易实现的方法b
3. 实现一个随机样本产生器
4. 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
5. 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
6. 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。