/**
*
*/
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 閱讀(267)
評論(0) 編輯 收藏 所屬分類:
java