Skip to content

Commit 5af7b23

Browse files
byhiegbyhieg
committed
添加排序算法，选择，插入，冒泡，快排
1 parent a34b33c commit 5af7b23

6 files changed

Lines changed: 269 additions & 0 deletions

File tree

‎src/main/java/cn/byhieg/algorithmtutorial/Sort.java‎

Lines changed: 176 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,176 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
/**
4+
* Created by shiqifeng on 2017/3/28.
5+
* Mail [email protected]
6+
*/
7+
public class Sort {
8+
9+
/**
10+
* 选择排序，每一轮排序，选择数组中数字最小的那一个放到指定的位置上。
11+
* 时间复杂度o(n^2),无论数组顺序如何都要选择一个最小的值，因为数组的是否有序，不影响时间复杂度
12+
* 空间复杂度o(1)
13+
* @param nums
14+
*/
15+
public void chooseSort(int[] nums) {
16+
int length = nums.length;
17+
for (int i = 0; i < length; i++) {
18+
int min = i;//申请额外的空间o(1)
19+
for (int j = i + 1; j < length; j++) {
20+
if (nums[min] > nums[j]) {
21+
min = j;
22+
}
23+
}
24+
//将最小的下标代表的数与i位置的进行交换
25+
int tmp = nums[i];
26+
nums[i] = nums[min];
27+
nums[min] = tmp;
28+
}
29+
}
30+
31+
/**
32+
* 直接插入排序，每一轮排序，都是在i坐标之前，包括i坐标的序列是有序的，但是并不是最终的排序位置。
33+
* 时间复杂度o（n^2),对于第二重循环，只会在非有序的环境下才会执行每个元素后移，因此针对有序的数组，时间复杂度最好的情况是o(N)。
34+
* 空间复杂度o(1)
35+
* @param nums
36+
*/
37+
public void insertDirectlySort(int[] nums) {
38+
int length = nums.length;
39+
for (int i = 1; i < length; i++) {
40+
for (int j = i ; j > 0; j --) {
41+
if (nums[j] < nums[j - 1]) {
42+
int tmp = nums[j - 1];
43+
nums[j - 1] = nums[j];
44+
nums[j] = tmp;
45+
}
46+
}
47+
}
48+
}
49+
50+
/**
51+
* 折半插入排序，针对直接排序而言，每一个要插入的元素都是插入在有序的数组中，因此，只需要查找到插入的位置即可，查找的方式利用二分查找
52+
* 时间复杂度和直接插入是一样的，只是快在了查找的过程中，还是o(N^2),最好的环境下是o（N）
53+
* 空间复杂度还是o(1)
54+
* @param nums
55+
*/
56+
public void insertBinarySort(int[] nums) {
57+
int length = nums.length;
58+
for (int i = 1; i < length;i++) {
59+
int tmp = nums[i];
60+
int low = 0;
61+
int high = i - 1;
62+
while (low <= high) {
63+
int mid = (low + high) / 2;
64+
if (tmp < nums[mid]) {
65+
high = mid - 1;
66+
}else{
67+
low = mid + 1;
68+
}
69+
}
70+
71+
for (int j = i; j >= low + 1;j--) {
72+
nums[j] = nums[j - 1];
73+
}
74+
nums[low] = tmp;
75+
}
76+
}
77+
78+
/**
79+
* 冒泡排序，每i轮排序，就是不断交换两个元素，直到将最大的元素放到n - i的位置上
80+
* 这种实现是按照算法定义的，但是效率是最低的
81+
* 时间复杂度o(n^2)
82+
* 空间复杂度o(1)
83+
* @param nums
84+
*/
85+
public void bubbleSort1(int[] nums) {
86+
int length = nums.length;
87+
for (int i = 1 ; i < length;i++) {
88+
for (int j = 0 ; j < length - i;j++) {
89+
if (nums[j] > nums[j + 1]) {
90+
int tmp = nums[j];
91+
nums[j] = nums[j + 1];
92+
nums[j+1] = tmp;
93+
}
94+
}
95+
}
96+
}
97+
98+
/**
99+
* 冒泡排序，高效率实现，因为只需要用一个flag变量来记录本次的排序，是否修改
100+
* 如果没有修改，说明已经有序
101+
* @param nums
102+
*/
103+
public void bubbleSort2(int[] nums) {
104+
int length = nums.length;
105+
boolean flag = true;
106+
while (flag) {
107+
flag = false;
108+
for (int j = 0 ; j < length - 1;j++) {
109+
if (nums[j] > nums[j + 1]) {
110+
int tmp = nums[j];
111+
nums[j] = nums[j + 1];
112+
nums[j + 1] = tmp;
113+
flag = true;
114+
}
115+
}
116+
length -- ;
117+
}
118+
}
119+
120+
/**
121+
* 快速排序，选定一个切分元素，每一轮排序后，都保证切分元素之前的元素都小于切分元素，切分元素之后的元素都大于切分元素
122+
*
123+
* @param nums
124+
*/
125+
public void quickSort(int[] nums) {
126+
int low = 0;
127+
int high = nums.length - 1;
128+
sort(nums, low, high);
129+
}
130+
131+
/**
132+
* 快速排序的递归实现
133+
* @param nums
134+
* @param low
135+
* @param high
136+
*/
137+
public void sort(int[] nums, int low, int high) {
138+
if (low >= high) return;
139+
int j = partition(nums, low, high);
140+
sort(nums, low, j - 1);
141+
sort(nums, j + 1, high);
142+
}
143+
144+
/**
145+
* 快速排序的辅助方法，来对排序的数组，进行切分,
146+
* @param nums
147+
* @param low
148+
* @param high
149+
* @return
150+
*/
151+
public int partition(int[] nums, int low, int high) {
152+
int i = low;
153+
int j = high;
154+
int x = nums[i];
155+
while (i < j) {
156+
//从右向左找到nums[j]小于x的元素
157+
while (i < j && nums[j] > x) j-- ;
158+
if (i < j) {
159+
nums[i] = nums[j];
160+
i++;
161+
}
162+
163+
//从左向右找到nums[i]大于x的元素
164+
while (i < j && nums[i] < x) i++;
165+
if (i < j) {
166+
nums[j] = nums[i];
167+
j--;
168+
}
169+
}
170+
nums[i] = x;
171+
return i;
172+
}
173+
174+
175+
176+
}

‎src/main/java/cn/byhieg/designpatterntutorial/proxy/dynamicproxy/Client.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package cn.byhieg.designpatterntutorial.proxy.dynamicproxy;
2+
3+
4+
import java.lang.reflect.Proxy;
5+
6+
/**
7+
* Created by shiqifeng on 2017/3/17.
8+
* Mail [email protected]
9+
*/
10+
public class Client {
11+
12+
public static void main(String[] args) {
13+
Subject realSubject = new RealSubject();
14+
DynamicProxy proxy = new DynamicProxy(realSubject);
15+
ClassLoader classLoader = realSubject.getClass().getClassLoader();
16+
Subject subject = (Subject) Proxy.newProxyInstance(classLoader, new Class[]{Subject.class}, proxy);
17+
subject.visit();
18+
}
19+
}

‎src/main/java/cn/byhieg/designpatterntutorial/proxy/dynamicproxy/DynamicProxy.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,11 @@
1010
public class DynamicProxy implements InvocationHandler {
1111
private Object object;
1212

13+
14+
public DynamicProxy(Object object) {
15+
this.object = object;
16+
}
17+
1318
@Override
1419
public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
1520
Object result = method.invoke(object, args);

‎src/main/java/cn/byhieg/designpatterntutorial/proxy/dynamicproxy/RealSubject.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package cn.byhieg.designpatterntutorial.proxy.dynamicproxy;
2+
3+
4+
/**
5+
* Created by shiqifeng on 2017/3/17.
6+
* Mail [email protected]
7+
*/
8+
public class RealSubject implements Subject {
9+
10+
private String name = "byhieg";
11+
@Override
12+
public void visit() {
13+
System.out.println(name);
14+
}
15+
}

‎src/main/java/cn/byhieg/designpatterntutorial/proxy/dynamicproxy/Subject.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package cn.byhieg.designpatterntutorial.proxy.dynamicproxy;
2+
3+
/**
4+
* Created by shiqifeng on 2017/3/17.
5+
* Mail [email protected]
6+
*/
7+
public interface Subject {
8+
9+
void visit();
10+
}

‎src/test/java/cn/byhieg/algorithmtutorialtest/SortTest.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package cn.byhieg.algorithmtutorialtest;
2+
3+
import cn.byhieg.algorithmtutorial.Sort;
4+
import junit.framework.TestCase;
5+
6+
/**
7+
* Created by shiqifeng on 2017/3/28.
8+
* Mail [email protected]
9+
*/
10+
public class SortTest extends TestCase {
11+
int [] nums;
12+
public void setUp() throws Exception {
13+
super.setUp();
14+
nums = new int[]{10, 20, 2, 3, 1, 100, 45, 22, 51, 21};
15+
}
16+
17+
public void tearDown() throws Exception {
18+
for (int i = 0 ; i < nums.length;i++){
19+
System.out.print(nums[i] + " ");
20+
}
21+
}
22+
23+
// public void testChooseSort() throws Exception {
24+
// new Sort().chooseSort(nums);
25+
// }
26+
27+
28+
// public void testInsertDirectlySort() throws Exception {
29+
// new Sort().insertDirectlySort(nums);
30+
// }
31+
32+
// public void testInsertBinarySort() throws Exception {
33+
// new Sort().insertBinarySort(nums);
34+
// }
35+
36+
// public void testBubbleSort() throws Exception {
37+
// new Sort().bubbleSort2(nums);
38+
// }
39+
40+
public void testQuickSort() throws Exception {
41+
new Sort().quickSort(nums);
42+
}
43+
44+
}

0 commit comments

Comments
 (0)