Skip to content

Commit 02662fd

Browse files
jxnu-liguobinjxnu-liguobin
committed
补充
1 parent e185a3c commit 02662fd

6 files changed

Lines changed: 833 additions & 698 deletions

File tree

‎Java-Learning-Summary/src/cn/edu/jxnu/questions/MySQL.md‎

Lines changed: 560 additions & 532 deletions
Large diffs are not rendered by default.

‎Java-Learning-Summary/src/cn/edu/jxnu/questions/倒排索引.jpg‎

21 KB
Loading

‎Java-Learning-Summary/src/cn/edu/jxnu/sort/BubbleSort.java‎

Lines changed: 70 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,70 @@
1-
package cn.edu.jxnu.sort;
2-
3-
/**
4-
* Copyright © 2018 梦境迷离. All rights reserved.
5-
*
6-
* @description:
7-
* @Package: cn.edu.jxnu.sort
8-
* @author: 梦境迷离
9-
* @date: 2018年3月28日 上午9:52:25
10-
*/
11-
12-
public class BubbleSort extends Constant {
13-
14-
public static void main(String[] args) throws Exception {
15-
Constant.printResult(new BubbleSort().sort(Constant.array, Constant.len));
16-
}
17-
18-
/**
19-
* 原始版本冒泡排序
20-
*/
21-
@Override
22-
public Object[] sort(Object[] array, int len) {
23-
for (int i = 0; i < array.length - 1; i++) {// 外层循环控制排序趟数
24-
for (int j = 0; j < array.length - 1 - i; j++) {//// 内层循环控制每一趟排序多少次
25-
if ((int) array[j] > (int) array[j + 1]) {
26-
Object temp = array[j];
27-
array[j] = array[j + 1];
28-
array[j + 1] = temp;
29-
}
30-
}
31-
}
32-
return array;
33-
}
34-
35-
}
1+
package cn.edu.jxnu.sort;
2+
3+
/**
4+
* Copyright © 2018 梦境迷离. All rights reserved.
5+
*
6+
* @description:
7+
* @Package: cn.edu.jxnu.sort
8+
* @author: 梦境迷离
9+
* @date: 2018年3月28日 上午9:52:25
10+
*/
11+
12+
public class BubbleSort extends Constant {
13+
14+
private static long time = 0l;
15+
private static long time2 = 0l;
16+
17+
public static void main(String[] args) throws Exception {
18+
Constant.printResult(new BubbleSort().sort(Constant.array2, Constant.len));// array:13474,array2:12832 相差明显
19+
Constant.printResult(new BubbleSort().sort2(Constant.array2, Constant.len));// array:1284,array2:1283
20+
System.out.println("没有优化：" + time);
21+
System.out.println("优化：" + time2);
22+
}
23+
24+
/**
25+
* 原始版
26+
*/
27+
@Override
28+
public Object[] sort(Object[] array, int len) {
29+
long t = System.nanoTime();
30+
for (int i = 0; i < array.length - 1; i++) {// 外层循环控制排序趟数
31+
for (int j = 0; j < array.length - 1 - i; j++) {// 内层循环控制每一趟排序多少次
32+
if ((int) array[j] > (int) array[j + 1]) {
33+
Object temp = array[j];
34+
array[j] = array[j + 1];
35+
array[j + 1] = temp;
36+
}
37+
}
38+
}
39+
time = System.nanoTime() - t;
40+
return array;
41+
}
42+
43+
/**
44+
* 优化版
45+
*/
46+
@Override
47+
public Object[] sort2(Object[] array, int len) {
48+
long t = System.nanoTime();
49+
boolean flag = false;
50+
for (int i = 0; i < array.length; i++) {
51+
flag = true;
52+
// 思路是每次进下一趟冒泡的时候给flag设置true,如果被修改说明还有元素没有被排序，继续重复操作
53+
// 如果经过一趟下来，没有元素被交换【没有设置flag=false】,此时说明元素全部有序，直接退出
54+
for (int j = 0; j < array.length - 1 - i; j++) {
55+
if ((int) array[j] > (int) array[j + 1]) {
56+
Object temp = array[j];
57+
array[j] = array[j + 1];
58+
array[j + 1] = temp;
59+
flag = false;
60+
}
61+
}
62+
if (flag) {
63+
break;
64+
}
65+
}
66+
time2 = System.nanoTime() - t;
67+
return array;
68+
}
69+
70+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/sort/Constant.java‎

Lines changed: 47 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,30 +1,47 @@
1-
package cn.edu.jxnu.sort;
2-
3-
import java.util.Arrays;
4-
import java.util.stream.Collectors;
5-
6-
/**
7-
* 定义排序用的常量,公共方法
8-
*
9-
*
10-
* @time 2018年3月24日14:39:51
11-
*/
12-
public abstract class Constant {
13-
14-
public static final Object[] array = { 8, 34, 64, 51, 33, 22, 44, 55, 88, 1, 0, 2, 2 };
15-
public static final int len = array.length;
16-
17-
public static void printResult(Object[] array) throws Exception {
18-
if (array == null || array.length == 0)
19-
throw new Exception("no element or invalid element in array");
20-
// java 8 lambda
21-
System.out.println(Arrays.stream(array).map(x -> x.toString()).collect(Collectors.joining(",", "[", "]")));
22-
}
23-
24-
/**
25-
* @author 梦境迷离
26-
* @description 子类需要强转。缺点
27-
* @time 2018年4月8日
28-
*/
29-
public abstract Object[] sort(Object[] array, int len);
30-
}
1+
package cn.edu.jxnu.sort;
2+
3+
import java.util.Arrays;
4+
import java.util.stream.Collectors;
5+
6+
/**
7+
* 定义排序用的常量,公共方法
8+
*
9+
* 这里最好使用泛型类，更通用
10+
*
11+
*
12+
* @time 2018年3月24日14:39:51
13+
*/
14+
public abstract class Constant {
15+
16+
public static final Object[] array = { 8, 34, 64, 51, 33, 22, 44, 55, 88, 1, 0, 2, 2 };
17+
// 有序数组
18+
public static final Object[] array2 = { 0, 1, 2, 2, 8, 22, 33, 34, 44, 51, 55, 64, 88 };
19+
public static final int len = array.length;
20+
21+
public static void printResult(Object[] array) throws Exception {
22+
if (array == null || array.length == 0)
23+
throw new Exception("no element or invalid element in array");
24+
// java 8 lambda
25+
System.out.println(Arrays.stream(array).map(x -> x.toString()).collect(Collectors.joining(",", "[", "]")));
26+
}
27+
28+
/**
29+
* 原始版
30+
*
31+
* @param array
32+
* @param len
33+
* @return
34+
*/
35+
public abstract Object[] sort(Object[] array, int len);
36+
37+
/**
38+
* 优化版
39+
*
40+
* @param array
41+
* @param len
42+
* @return
43+
*/
44+
public Object[] sort2(Object[] array, int len) {
45+
return new Object[0];
46+
}
47+
}

‎Java-Learning-Summary/src/cn/edu/jxnu/sort/CountSort.java‎

Lines changed: 65 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -1,62 +1,65 @@
1-
package cn.edu.jxnu.sort;
2-
3-
/**
4-
* @author 梦境迷离
5-
* @description 计数排序
6-
*
7-
* 计数排序 计数排序适用数据范围 计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如
8-
* [0~100]，[10000~19999] 这样的数据。 过程分析 计数排序的基本思想是：
9-
* 对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。 所以可以直接把 arr[i]
10-
* 放到它输出数组中的位置上。假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。 下面给出两种实现：
11-
* 算法流程（1） 需要三个数组: 待排序数组 int[] arr = new int[]{4,3,6,3,5,1}; 辅助计数数组
12-
* int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
13-
* 输出数组 int[] res = new int[arr.length]; 1.求出待排序数组的最大值max=6，
14-
* 最小值min=1 2.实例化辅助计数数组help，help数组中每个下标对应arr中的一个元素，
15-
* help用来记录每个元素出现的次数 3.计算 arr 中每个元素在help中的位置 position = arr[i] -
16-
* min，此时 help = [1,0,2,1,1,1]; （3出现了两次，2未出现） 4.根据 help
17-
* 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]
18-
*
19-
* 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
20-
*
21-
* @time 2018年4月8日
22-
*/
23-
public class CountSort extends Constant {
24-
25-
public static void main(String[] args) throws Exception {
26-
Constant.printResult(new CountSort().sort(Constant.array, Constant.len));
27-
28-
}
29-
30-
@Override
31-
public Object[] sort(Object[] array, int len) {
32-
33-
return countSort(array);
34-
}
35-
36-
public static Object[] countSort(Object[] arr) {
37-
38-
int max = Integer.MIN_VALUE;
39-
int min = Integer.MAX_VALUE;
40-
// 找出数组中的最大最小值
41-
for (int i = 0; i < arr.length; i++) {
42-
max = Math.max(max, (int) arr[i]);
43-
min = Math.min(min, (int) arr[i]);
44-
}
45-
// 比max大1
46-
int help[] = new int[max - min + 1];
47-
// 找出每个数字出现的次数
48-
for (int i = 0; i < arr.length; i++) {
49-
int mapPos = (int) arr[i] - min;
50-
help[mapPos]++;
51-
}
52-
int index = 0;
53-
for (int i = 0; i < help.length; i++) {
54-
// 因为可能有重复的数据
55-
while (help[i]-- > 0) {
56-
arr[index++] = i + min;
57-
}
58-
}
59-
return arr;
60-
}
61-
62-
}
1+
package cn.edu.jxnu.sort;
2+
3+
/**
4+
* @author 梦境迷离
5+
* @description 计数排序
6+
*
7+
* 计数排序 计数排序适用数据范围 计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如
8+
* [0~100]，[10000~19999] 这样的数据。
9+
* 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
10+
*
11+
* @time 2018年4月8日
12+
*/
13+
public class CountSort extends Constant {
14+
15+
private static long time = 0l;
16+
17+
public static void main(String[] args) throws Exception {
18+
Constant.printResult(new CountSort().sort(Constant.array2, Constant.len));
19+
System.out.println("耗费时间："+time);//array1：18606,array2：18927 几乎相同
20+
21+
}
22+
23+
@Override
24+
public Object[] sort(Object[] array, int len) {
25+
26+
return countSort(array);
27+
}
28+
29+
/**
30+
* 计数排序
31+
*
32+
* 1.得到最大值与最小值，并计算最大值与最小值之差，制造桶，此时桶的下标i并非真正的元素，而是元素与min之差
33+
* 2.统计每个元素出现的次数，并记录在桶中
34+
* 3.对桶中的元素进行取出，注意有重复的元素，而此时元素是i与min之和
35+
*
36+
*/
37+
public static Object[] countSort(Object[] arr) {
38+
long t = System.nanoTime();
39+
40+
int max = Integer.MIN_VALUE;
41+
int min = Integer.MAX_VALUE;
42+
// 找出数组中的最大最小值
43+
for (int i = 0; i < arr.length; i++) {
44+
max = Math.max(max, (int) arr[i]);
45+
min = Math.min(min, (int) arr[i]);
46+
}
47+
// 比max大1
48+
int help[] = new int[max - min + 1];
49+
// 找出每个数字出现的次数
50+
for (int i = 0; i < arr.length; i++) {
51+
int mapPos = (int) arr[i] - min;
52+
help[mapPos]++;
53+
}
54+
int index = 0;
55+
for (int i = 0; i < help.length; i++) {
56+
// 因为可能有重复的数据，所以需要循环
57+
while (help[i]-- > 0) {
58+
arr[index++] = i + min;
59+
}
60+
}
61+
62+
time = System.nanoTime() - t;
63+
return arr;
64+
}
65+
}

0 commit comments

Comments
 (0)