随笔-12  评论-6  文章-0  trackbacks-0
/**
 * 
 
*/
package com.zx.ww.arraysort;

import java.text.Collator;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Comparator;
import java.util.Locale;

/**
 * 
@author xue
 * 2014年9月24日
 
*/
public class QuickSort {

    
public static void main(String[] args) {
        
for (int i = 0; i < 10; i++) {
            test();
        }
    }
    
    
public static void test() {
        
        
int len = 8000000;
        
int[] array = new int[len];
        
for (int i = 0; i < len; i++) {
            array[i] 
= (int)(Math.random()*10000);
        }
        
        Calendar cal_before 
= Calendar.getInstance();
        
double before = cal_before.getTimeInMillis();
        System.out.println(cal_before.getTime());
        quickSort(array, 
0, array.length-1);
        
        Calendar cal_after 
= Calendar.getInstance();
        
double after = cal_after.getTimeInMillis();
        System.out.println(cal_after.getTime());
        
        
        
double time = after-before;
        System.out.println(
"用时:" + time + "ms");
        System.out.println(
"==================================");
        
    }
    
    
public static void quickSort(int[] array, int left, int right) {
        
if(left < right) {
            
int privot = getPrivot(array, left, right);
            quickSort(array, left, privot
-1);
            quickSort(array, privot
+1, right);
        }
        
    }
    
    
    
//将数组划分为两个数组,左边的数组都比中轴privot小,右边的都比中轴privot大
    public static int getPrivot(int[] array, int left, int right) {
        
        
int tmp = array[left];
        
        
while(left < right) {
            
            
while(left < right && array[right] >= tmp) {
                right
--;
            }
            
            array[left] 
= array[right];
            
            
while(left < right && array[left] <= tmp) {
                left
++;
            }
            
            array[right] 
= array[left];
            
        }
        
        array[left] 
= tmp;
        
        
return left;
    }
    
}

运行十次输出的结果:

Thu Sep 25 13:09:40 CST 2014
Thu Sep 
25 13:09:41 CST 2014
用时:
1613.0ms
==================================
Thu Sep 
25 13:09:41 CST 2014
Thu Sep 
25 13:09:43 CST 2014
用时:
1614.0ms
==================================
Thu Sep 
25 13:09:43 CST 2014
Thu Sep 
25 13:09:45 CST 2014
用时:
1691.0ms
==================================
Thu Sep 
25 13:09:45 CST 2014
Thu Sep 
25 13:09:47 CST 2014
用时:
1622.0ms
==================================
Thu Sep 
25 13:09:47 CST 2014
Thu Sep 
25 13:09:48 CST 2014
用时:
1621.0ms
==================================
Thu Sep 
25 13:09:49 CST 2014
Thu Sep 
25 13:09:50 CST 2014
用时:
1615.0ms
==================================
Thu Sep 
25 13:09:50 CST 2014
Thu Sep 
25 13:09:52 CST 2014
用时:
1614.0ms
==================================
Thu Sep 
25 13:09:52 CST 2014
Thu Sep 
25 13:09:54 CST 2014
用时:
1632.0ms
==================================
Thu Sep 
25 13:09:54 CST 2014
Thu Sep 
25 13:09:55 CST 2014
用时:
1614.0ms
==================================
Thu Sep 
25 13:09:56 CST 2014
Thu Sep 
25 13:09:57 CST 2014
用时:
1614.0ms
==================================
上述是快速排序八百万条数据用时基本在1.6s左右。

接下来看冒泡排序:
/**
 * 
 
*/
package com.zx.ww.arraysort;

import java.text.Collator;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Comparator;
import java.util.Locale;

/**
 * 
@author wuwei
 * 2014年9月24日
 
*/
public class BubbleSort {

    
public static void main(String[] args) {
        
        
for (int i = 0; i < 5; i++) {
            test();
        }
        
    }
    
    
public static void test() {
        
        
int len = 80000;
        
int[] array = new int[len];
        
for (int i = 0; i < array.length; i++) {
            array[i] 
= (int)(Math.random()*10000);
        }
        
        Calendar calBefore 
= Calendar.getInstance();
        System.out.println(calBefore.getTime());
        
        bubbleSort(array);
        
        Calendar calAfter 
= Calendar.getInstance();
        System.out.println(calAfter.getTime());
        
        System.out.println(
"总共用时" + (calAfter.getTimeInMillis()-calBefore.getTimeInMillis()) + "ms");
        
        System.out.println(
"==========================");
        
    }
    
    
public static void bubbleSort(int[] array) {
        
        
int tmp;
        
for (int i = 0; i < array.length; i++) {
            
for (int j = 0; j < array.length-i-1; j++) {
                
                
if(array[j] > array[j+1]) {
                    tmp 
= array[j+1];
                    array[j
+1= array[j];
                    array[j] 
= tmp;
                }
                
            }
        }
    }
    
}
运行五次输出如下结果:
Thu Sep 25 14:44:14 CST 2014
Thu Sep 
25 14:44:23 CST 2014
总共用时8822ms
==========================
Thu Sep 
25 14:44:23 CST 2014
Thu Sep 
25 14:44:32 CST 2014
总共用时8829ms
==========================
Thu Sep 
25 14:44:32 CST 2014
Thu Sep 
25 14:44:41 CST 2014
总共用时8915ms
==========================
Thu Sep 
25 14:44:41 CST 2014
Thu Sep 
25 14:44:50 CST 2014
总共用时8748ms
==========================
Thu Sep 
25 14:44:50 CST 2014
Thu Sep 
25 14:44:58 CST 2014
总共用时8529ms
==========================
冒泡排序八万条数据用时接近9s。

需要注意的是快速排序是八百万条数据只用了1.6s左右。


posted on 2014-09-25 13:09 小人物_Amor 阅读(101) 评论(0)  编辑  收藏 所属分类: java

只有注册用户登录后才能发表评论。


网站导航: