Fork me on GitHub

比较冒泡法、选择法以及二叉树排序的性能区别

创建4万个随机数,然后分别用冒泡法、选择法、二叉树3种排序算法进行排序,比较哪种更快。

mc_07093.java

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
public static void main(String[] args) {
//初始化随机数
int total = 40000;
System.out.println("初始化一个长度是"+total+"的随机数字的数组");
int[] originalNumbers = new int[total];
for (int i = 0; i < originalNumbers.length; i++) {
originalNumbers[i] = (int)(Math.random()*total);
}
System.out.println("初始化完毕");
System.out.println("接下来分别用3种算法进行排序");
//从初始化了的随机数组复制过来,以保证,每一种排序算法的目标数组,都是一样的
int[] use4sort;
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersBySelection= performance(new SelectionSort(use4sort),"选择法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByBubbling=performance(new BubblingSort(use4sort),"冒泡法");
use4sort= Arrays.copyOf(originalNumbers, originalNumbers.length);
int[] sortedNumbersByTree=performance(new TreeSort(use4sort),"二叉树");
System.out.println("查看排序结果,是否是不同的数组对象");
System.out.println(sortedNumbersBySelection);
System.out.println(sortedNumbersByBubbling);
System.out.println(sortedNumbersByTree);
System.out.println("查看排序结果,内容是否相同");
System.out.println("比较 选择法 和 冒泡法 排序结果:");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByBubbling));
System.out.println("比较 选择法 和 二叉树 排序结果:");
System.out.println(Arrays.equals(sortedNumbersBySelection, sortedNumbersByTree));
}
interface Sort{
void sort();
int[] values();
}
static class SelectionSort implements Sort{
int numbers[];
SelectionSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length-1; j++) {
for (int i = j+1; i < numbers.length; i++) {
if(numbers[i]<numbers[j]){
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
}
@Override
public int[] values() {
// TODO Auto-generated method stub
return numbers;
}
}
static class BubblingSort implements Sort{
int numbers[];
BubblingSort(int [] numbers){
this.numbers = numbers;
}
@Override
public void sort() {
for (int j = 0; j < numbers.length; j++) {
for (int i = 0; i < numbers.length-j-1; i++) {
if(numbers[i]>numbers[i+1]){
int temp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
}
}
@Override
public int[] values() {
// TODO Auto-generated method stub
return numbers;
}
}
static class TreeSort implements Sort{
int numbers[];
mc_07092 n;
TreeSort(int [] numbers){
n =new mc_07092();
this.numbers = numbers;
}
@Override
public void sort() {
for (int i : numbers) {
n.add(i);
}
}
@Override
public int[] values() {
List<Object> list = n.values();
int sortedNumbers[] = new int[list.size()];
for (int i = 0; i < sortedNumbers.length; i++) {
sortedNumbers[i] = Integer.parseInt(list.get(i).toString());
}
return sortedNumbers;
}
}
private static int[] performance(Sort algorithm, String type) {
long start = System.currentTimeMillis();
algorithm.sort();
int sortedNumbers[] = algorithm.values();
long end = System.currentTimeMillis();
System.out.printf("%s排序,一共耗时 %d 毫秒%n",type,end-start);
return sortedNumbers;
}

mc_07092.java

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
// 左子节点
public mc_07092 leftNode;
// 右子节点
public mc_07092 rightNode;
// 值
public Object value;
// 插入 数据
public void add(Object v) {
// 如果当前节点没有值,就把数据放在当前节点上
if (null == value)
value = v;
// 如果当前节点有值,就进行判断,新增的值与当前值的大小关系
else {
// 新增的值,比当前值小或者相同
if ((Integer) v -((Integer)value) <= 0) {
if (null == leftNode)
leftNode = new mc_07092();
leftNode.add(v);
}
// 新增的值,比当前值大
else {
if (null == rightNode)
rightNode = new mc_07092();
rightNode.add(v);
}
}
}
// 中序遍历所有的节点
public List<Object> values() {
List<Object> values = new ArrayList<>();
// 左节点的遍历结果
if (null != leftNode)
values.addAll(leftNode.values());
// 当前节点
values.add(value);
// 右节点的遍历结果
if (null != rightNode)
values.addAll(rightNode.values());
return values;
}
public static void main(String[] args) {
int randoms[] = new int[] { 67, 7, 30, 73, 10, 0, 78, 81, 10, 74 };
mc_07092 roots = new mc_07092();
for (int number : randoms) {
roots.add(number);
}
System.out.println(roots.values());
}

Your support will encourage me to continue to create!