使用JAVA直观感受快速排序与冒泡排序的性能差异

初学算法，肯定会编写排序算法

其中两个最为有名的就是冒泡排序和快速排序

理论上冒泡排序的时间复杂度为O(N^2)，快速排序的时间复杂度为O(NlogN)

下面本门使用JAVA，分别编写三段排序程序

对十万个0-9999的整数进行一次冒泡排序
对十万个0-9999的整数进行1000次快速排序，使用递归完成
对十万个0-9999的整数进行1000次快速排序，使用堆栈完成

对十万个0-9999的整数进行一次冒泡排序：

package sort;

import java.util.Date;

public class PopSort {

public static void main(String[] args){

int N=100000;

int[] array=new int[N];

for(int i=0;i<N;i++)

array[i]=(int) (Math.random()*9999);

Date begin=new Date();

for(int i=N-1;i>1;i--){

for(int j=0;j<i;j++){

if(array[j]>array[j+1]){

int tmp=array[j];

array[j]=array[j+1];

array[j+1]=tmp;

}

Date end=new Date();

System.out.println("使用冒泡排序，对 " +N+ "个整数进行排序，用时：" +String.valueOf(end.getTime()-begin.getTime())+ "毫秒");

for(int i=0;i<100;i++)

System.out.print(array[i]+" ");

}

执行结果：

下面是使用递归方法的快速排序：

package sort;

import java.util.Date;

public class QuickSort {

public static void main(String[] args){

int K=1000;

int N=100000;

Date begin = new Date();

for(int num=0;num<K;num++){

int[] array=new int[N];

for(int i=0;i<N;i++)

array[i]=(int) (Math.random()*9999);

sort(array,0,array.length-1);

}

Date end=new Date();

long time=end.getTime()-begin.getTime();

System.out.println("使用递归方式进行快速排序，对 " +N+ "个整数进行排序 " +K+ "次，用时：" +String.valueOf(time)+ "毫秒\n平均用时："+time/K+"毫秒");

}

private static void sort(int[] array,int begin,int end){

int right=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){

int tmp=array[left];

array[left]=array[right];

array[right]=tmp;

}else if(right!=begin){

int tmp=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);

}

执行结果：

最后一段程序是使用数据结构栈来实现的非递归快速排序算法：

package sort;

import java.util.Date;

import java.util.Stack;

/**

* 使用栈而不是递归来实现快排

* @author newflydd@189.cn

* Time : 2016年1月8日下午9:51:49

*/

public class QuickSort2 {

public static void main(String[] args) {

Date begin = new Date();

Date end=null;

int K=1000;

int N=100000;

for(int num=0;num<K;num++){

int[] array=new int[N];

for(int i=0;i<N;i++)

array[i]=(int) (Math.random()*9999);

Stack<Node> stack=new Stack<Node>();

stack.add(new Node(0,N-1));

while(!stack.isEmpty()){

Node node=stack.pop();

int right=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){

int tmp=array[left];

array[left]=array[right];

array[right]=tmp;

}else if(right!=node.begin){

int tmp=array[node.begin];

array[node.begin]=array[right];

array[right]=tmp;

}

if(left-1>node.begin)

stack.push(new Node(node.begin,left-1));

if(node.end>right+1)

stack.push(new Node(right+1,node.end));

}

end=new Date();

long time=end.getTime()-begin.getTime();

System.out.println("使用数据结构栈进行快速排序，对 " +N+ "个整数进行排序 " +K+ "次，用时：" +String.valueOf(time)+ "毫秒\n平均用时："+time/K+"毫秒");

}

class Node{

public int begin;

public int end;

public Node(int begin,int end){

this.begin=begin;

this.end=end;

}

执行结果：

综上所述，可以直观的看出来

复杂度为O(N^2)的冒泡排序速度相当慢，一次排序就要18秒，而复杂度为O(NlogN)的快速排序基本上20毫秒内就搞定，这就是算法的力量啊。
递归函数在这里并不会影响性能，直观，简洁的递归算法是相当实用的，除非动态规划算法一定要将递归转变成循环，否则大多数情况下并不需要改变递归方法，而非递归算法因为会引入其他数据结构，有可能导致程序还会稍稍有些额外开支。

本文来自：http://www.hexcode.cn/article/4090/show

巴特西

使用JAVA直观感受快速排序与冒泡排序的性能差异

最新文章

热门文章