使用JAVA直观感受快速排序与冒泡排序的性能差异
初学算法，肯定会编写排序算法
其中两个最为有名的就是冒泡排序和快速排序
理论上冒泡排序的时间复杂度为O(N^2)，快速排序的时间复杂度为O(NlogN)
下面本门使用JAVA，分别编写三段排序程序
-
对十万个0-9999的整数进行一次冒泡排序
-
对十万个0-9999的整数进行1000次快速排序，使用递归完成
-
对十万个0-9999的整数进行1000次快速排序，使用堆栈完成
对十万个0-9999的整数进行一次冒泡排序：
|
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
|
packagesort;
importjava.util.Date;
publicclassPopSort{
publicstaticvoidmain(String[]args){
intN=100000;
int[]array=newint[N];
for(inti=0;i<N;i++)
array[i]=(int)(Math.random()*9999);
Datebegin=newDate();
for(inti=N-1;i>1;i--){
for(intj=0;j<i;j++){
if(array[j]>array[j+1]){
inttmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
}
}
Dateend=newDate();
System.out.println("使用冒泡排序，对"+N+"个整数进行排序，用时："+String.valueOf(end.getTime()-begin.getTime())+"毫秒");
for(inti=0;i<100;i++)
System.out.print(array[i]+"");
}
}
|
执行结果：
下面是使用递归方法的快速排序：
|
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
|
packagesort;
importjava.util.Date;
publicclassQuickSort{
publicstaticvoidmain(String[]args){
intK=1000;
intN=100000;
Datebegin=newDate();
for(intnum=0;num<K;num++){
int[]array=newint[N];
for(inti=0;i<N;i++)
array[i]=(int)(Math.random()*9999);
sort(array,0,array.length-1);
}
Dateend=newDate();
longtime=end.getTime()-begin.getTime();
System.out.println("使用递归方式进行快速排序，对"+N+"个整数进行排序"+K+"次，用时："+String.valueOf(time)+"毫秒\n平均用时："+time/K+"毫秒");
}
privatestaticvoidsort(int[]array,intbegin,intend){
intright=end,left=begin;
while(right!=left){
for(;right>left;right--){
if(array[begin]>=array[right])
break;
}
for(;left<right;left++){
if(array[begin]<array[left])
break;
}
if(left!=right){
inttmp=array[left];
array[left]=array[right];
array[right]=tmp;
}elseif(right!=begin){
inttmp=array[begin];
array[begin]=array[left];
array[left]=tmp;
}
}
if(left-1>begin)
sort(array,begin,left-1);
if(right+1<end)
sort(array,right+1,end);
}
}
|
执行结果：
最后一段程序是使用数据结构栈来实现的非递归快速排序算法：
|
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
|
packagesort;
importjava.util.Date;
importjava.util.Stack;
/**
*使用栈而不是递归来实现快排
*@authornewflydd@189.cn
*Time:2016年1月8日下午9:51:49
*/
publicclassQuickSort2{
publicstaticvoidmain(String[]args){
Datebegin=newDate();
Dateend=null;
intK=1000;
intN=100000;
for(intnum=0;num<K;num++){
int[]array=newint[N];
for(inti=0;i<N;i++)
array[i]=(int)(Math.random()*9999);
Stack<Node>stack=newStack<Node>();
stack.add(newNode(0,N-1));
while(!stack.isEmpty()){
Nodenode=stack.pop();
intright=node.end,left=node.begin;
while(right!=left){
for(;right>left;right--)
if(array[node.begin]>=array[right])
break;
for(;left<right;left++)
if(array[node.begin]<array[left])
break;
if(left!=right){
inttmp=array[left];
array[left]=array[right];
array[right]=tmp;
}elseif(right!=node.begin){
inttmp=array[node.begin];
array[node.begin]=array[right];
array[right]=tmp;
}
}
if(left-1>node.begin)
stack.push(newNode(node.begin,left-1));
if(node.end>right+1)
stack.push(newNode(right+1,node.end));
}
}
end=newDate();
longtime=end.getTime()-begin.getTime();
System.out.println("使用数据结构栈进行快速排序，对"+N+"个整数进行排序"+K+"次，用时："+String.valueOf(time)+"毫秒\n平均用时："+time/K+"毫秒");
}
}
classNode{
publicintbegin;
publicintend;
publicNode(intbegin,intend){
this.begin=begin;
this.end=end;
}
}
|
执行结果：
综上所述，可以直观的看出来
-
复杂度为O(N^2)的冒泡排序速度相当慢，一次排序就要18秒，而复杂度为O(NlogN)的快速排序基本上20毫秒内就搞定，这就是算法的力量啊。
-
递归函数在这里并不会影响性能，直观，简洁的递归算法是相当实用的，除非动态规划算法一定要将递归转变成循环，否则大多数情况下并不需要改变递归方法，而非递归算法因为会引入其他数据结构，有可能导致程序还会稍稍有些额外开支。
本文来自：http://www.hexcode.cn/article/4090/show
优质内容筛选与推荐>>1、JS基础
2、libusb 源码阅读
3、线段树扫描线求矩形面积并
4、session校验是否登录
5、【开源】FloatingActionButton