选择排序
原理：i~n-1范围上，找到最小值并放在i位置，然后i+1~n-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
|
public static void selectionsort(int[] arr) {
//注意先想边界条件
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ n-1先选一个数
// 1 ~ n-1再选一个数
int N = arr.length;
for (int i = 0; i < N; i++) {
int minValueIndex = i;
for (int j = i + 1; j < N; j++) {
minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
}
swap(arr, i, minValueIndex);
}
}
//从第一个位置开始，依次和后面的比较，大的则索引位置数往后交换
public static void swap(int[] arr, int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
|
冒泡排序
原理：0~i范围上，相邻位置较大的数滚下去，最大值最终来到i位置，然后0~i-1范围上继续
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
|
插入排序
原理：0~i范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
//0~i-1有序了，新来的数【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) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = 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
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
| 1.你想要测的方法a(最优解)
2.实现复杂度不好但是容易实现的方法b(暴力解)
3.实现一个随机样本产生器(长度也随机、值也随机)
4.把方法a和方法b跑相同的输入样本，看看得到的结果是否一样
5.如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b
6.当样本数量很多时比对测试依然正确，可以确定方法a(最优解)已经正确。
关键是`第5步`，找到一个数据量小的错误样本，便于你去带入debug，然后把错误例子带入代码一步一步排查（Print大法、断点技术都可以）
```java
public static int[] randomArray(int n, int v) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
//Math.random()-> double ->[0,1)一个小数
//Math.random() * v-> double ->[0,V)一个小数，依然等概率
//(int)(Math.random() * v)->int ->0 1 2 3 ...v-1 等概率
arr[i] = (int) (Math.random() * v) + 1;
}
return arr;
}
public static int[] copyArray(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = arr[i];
}
return ans;
}
public static boolean sameArray(int[]arr1,int[]arr2){
for(int i = 0 ;i < arr1.length;i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
//随机数组最大长度
int N = 100;
//随机数组每个值在1~v之间随机
int V = 1000;
//测试次数
int testTimes = 5000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
//随机得到一个长度，长度在[0~N-1]
int n = (int) (Math.random() * N);
int[] arr = randomArray(n, V);
int[] arr1 = copyArray(arr);
int[] arr2 = copyArray(arr);
int[] arr3 = copyArray(arr);
selectionsort(arr1);
bubbleSort(arr2);
insertionSort(arr3);
if (!sameArray(arr1, arr2) || !sameArray(arr1, arr3)) {
System.out.println("出错了！");
}
}
}
```
|
