第一章

# Selection Sort

时间复杂度：
额外空间复杂度：

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++) {
            // find the smallest value and move it to the front
            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

# Bubble Sort

时间复杂度：
额外空间复杂度：

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int e = arr.length - 1; e > 0; e--) {
        for (int i = 0; i < e; i++) {
            if (arr[i] > arr[i + 1]) {
                // all swap again 
                swap(arr, i, i + 1);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# Insertion Sort

最差时间复杂度：
最好时间复杂度：
额外空间复杂度：

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

// 不用额外变量交换两个数
// i and j 一样的话会出错，所以不建议这么写
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

# EOR （位运算）

EOR 原理：无进位相加，顺序不重要
- 0^N == N and N^N == 0
- 异或运算满足交换律和结合率
非常快，贼快😎
一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数
- 方法就是全都 EOR，结果就是我们要找的那个数

public static void printOddTimesNum1(int[] arr) {
    int eor = 0;
    for (int cur : arr) {
        eor ^= cur;
    }
    System.out.println(eor);
}

1
2
3
4
5
6
7

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
- 先算出 a 和 b 的 EOR
- 找到 EOR 第一个为 1 的二进制位，意味着这个位置，a 和 b 不一样
- 找出所有这个位置为 1 的数字，计算 EOR‘，得到 a 或者是 b
- EOR ^ EOR'，得到 b 或者是 a

public static void printOddTimesNum2(int[] arr) {
    int eor = 0;
    for (int curNum : arr) {
        eor ^= curNum;
    }
    // eor = a ^ b
    // eor != 0
    // eor 必然有一个二进制位置是 1

    // 选最右侧的 1，先取反，然后补码，然后‘与’ （常规操作）
    int rightOne = eor & (~eor + 1);

    int eorHasOne = 0; // eor'
    for (int cur : arr) {
        if ((cur & rightOne) != 0) {
            eorHasOne ^= cur;
        }
    }
    System.out.println(eorHasOne + " " + (eor ^ eorHasOne));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Binary Search (二分法)

# 1. 在一个有序数组中，找某个数是否存在

线性的话，最差时间复杂度：
二分的话，最差时间复杂度：

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

e.g. 在1111111111112222222222233333333334444444，target = 3

# 3. 无序数组中，相邻数一定不相同，找局部最小值

不是只有有序数组可以二分
这个范围内，必定存在最小值，有峰谷：

之后取中间值 M, 如果 M-1 比 M 小，M+1 比 M 大，直接返回 M
如果 M 比 M - 1 大，遍历左边
如果 M 比 M + 1 大，遍历右边

# 对数器

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

public class Code01_SelectionSort {

	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++) {
				// find the smallest value and move it to the front
				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;
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	public static int[] generateRandomArray(int maxSize, int maxValue) {

		// Math.random() -> [0,1) 所有的小数，等概率返回一个
		// Math.random() * N -> [0, N) 所有的小数，等概率返回一个
		// (int)(Math.random * N) -> [0, N - 1)所有的整数，等概率返回一个
		
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			selectionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		selectionSort(arr);
		printArray(arr);
	}

}

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

# 递归

# 1. 系统上到底是怎么做的?

上次更新: 2022/12/04, 16:55:22

← Untitled 1→