算法图解中所有算法总结和java实现 · CTCSU/AlgorithmGraphExample@a187533 · GitHub
Skip to content

Commit a187533

Browse files
CTCSUCTCSU
committed
算法图解中所有算法总结和java实现
1 parent c9138d6 commit a187533

7 files changed

Lines changed: 163 additions & 0 deletions

File tree

‎.gitignore‎

Lines changed: 26 additions & 0 deletions

‎ReadMe.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
# 《算法图解》中涉及的算法的总结及java实现
2+
3+
## 二分查找：
4+
*算法目的：* 查找在有序数组中某给定值的位置
5+
*算法描述：* 当数组中元素有序排列时，通过比较数组的
6+

‎pom.xml‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>Algorithm</groupId>
8+
<artifactId>algorithmGraph</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
11+
<dependencies>
12+
<dependency>
13+
<groupId>junit</groupId>
14+
<artifactId>junit</artifactId>
15+
<version>4.12</version>
16+
</dependency>
17+
</dependencies>
18+
19+
20+
</project>

‎src/main/java/AlgorithmInGraph.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
2+
public interface AlgorithmInGraph {
3+
void showAlgorithm();
4+
}

‎src/main/java/BinarySearch.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
* 二分查找,
3+
* 查找在有序数组中某给定值的位置,
4+
* 算法复杂度为O(logn);
5+
*/
6+
@SuppressWarnings("unused")
7+
public class BinarySearch implements AlgorithmInGraph {
8+
public void showAlgorithm() {
9+
int [] array = new int[100];
10+
for(int i=0;i<100;i++ ){
11+
array[i] = i;
12+
}
13+
14+
printSearchResult(array,45);
15+
printSearchResult(array,105);
16+
printSearchResult(array,0);
17+
printSearchResult(array,99);
18+
19+
}
20+
21+
/**
22+
* @param sortedArray 已经排序好的数组
23+
* @param value 需要查询的值value
24+
* @return 返回值在有序数组中的索引,如果数组中不存在这个值,则返回-1;
25+
*/
26+
private int doBinarySearch(int [] sortedArray,int value){
27+
int right = sortedArray.length - 1;
28+
int left = 0;
29+
int middle;
30+
//这里=号容易被忽略
31+
while(right>= left){
32+
middle = (left+right)/2;
33+
if(sortedArray[middle] == value){
34+
return middle;
35+
}
36+
else if(sortedArray[middle] < value){
37+
left = middle+1;
38+
}
39+
else{
40+
right = middle-1;
41+
}
42+
}
43+
return -1;
44+
}
45+
46+
private void printSearchResult(int [] array,int value){
47+
System.out.println("在0-99的有序数组中," + value+"的位置是: \t" + doBinarySearch(array,value));
48+
}
49+
}

‎src/main/java/ChooseSort.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
import java.util.Arrays;
2+
import java.util.Random;
3+
4+
/**
5+
* 选择排序
6+
* 依次选择最小（大）的值放到对应的值
7+
* 算法复杂度为O（n^2）
8+
*/
9+
public class ChooseSort implements AlgorithmInGraph {
10+
11+
public void showAlgorithm() {
12+
int [] array = new int[10];
13+
Random random = new Random();
14+
for(int i = 0;i<10;i++){
15+
array[i] = random.nextInt(100);
16+
}
17+
System.out.println("排序前生成的数组的顺序是: \t" + Arrays.toString(array));
18+
sort(array);
19+
System.out.println("排序后的数组的顺序是: \t" + Arrays.toString(array));
20+
21+
}
22+
23+
/**
24+
* @param array 待排序的数组
25+
* 因为传进来的是数组，所以不需要返回，将数组排序好
26+
*/
27+
private void sort(int [] array){
28+
for(int i = 0;i<array.length;i++){
29+
int min = array[i];
30+
int index = i;
31+
for(int j = i;j<array.length;j++){
32+
if(min > array[j]){
33+
min = array[j];
34+
index = j;
35+
}
36+
}
37+
if(i != index){
38+
int temp = array[i];
39+
array[i] = array[index];
40+
array[index] = temp;
41+
}
42+
}
43+
}
44+
}

‎src/test/java/AlgorithmInGraphTest.java‎

Lines changed: 14 additions & 0 deletions

0 commit comments

Comments
 (0)