/**
*
*/
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 阅读(251)
评论(0) 编辑 收藏 所属分类:
java