由于閑來無事且突發奇想,每次都背各種排序的時間複雜度,一個結論看着太過單調,是以就想着測試一下每個算法處理一些大量資料所需要的真正時間。由于是用随機數生成的,是以肯定有誤差,圖一樂就好。
1、冒泡排序
時間複雜度:O(n2)
public static void main(String[] args) {
int arr [] = new int[1000000];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
long start = System.currentTimeMillis();
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
long end = System.currentTimeMillis();
System.out.println((end - start)/1000); //1484
}
這種算法跑出來的時間為1484秒,本來是毫秒,由于太長是以除了1000變成了秒。
在經過漫長的等待,中間還去打了把遊戲,最終差不多25分鐘,冒泡才将這100萬個數處理完。
2、選擇排序
時間複雜度:O(n2)
public static void main(String[] args) {
int arr [] = new int[1000000];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
long start = System.currentTimeMillis();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
long end = System.currentTimeMillis();
System.out.println((end - start)/1000); //1267
}
這種算法跑出來的時間為1267秒,21分鐘左右,跟冒泡的時間差不多。同樣是中間打了把遊戲,沒有辦法,實在太難等。
3、插入排序
時間複雜度:O(n2)
public static void main(String[] args) {
int arr [] = new int[1000000];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
long start = System.currentTimeMillis();
int startIndex = -1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
startIndex = i + 1;
break;
}
}
for (int i = startIndex; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
long end = System.currentTimeMillis();
System.out.println((end - start)/1000); //147
}
當我準備開第三把遊戲想着再等待10多分鐘的時候,插入排序居然兩分多鐘就處理好了,耗時147秒。
4、快速排序
時間複雜度:O(nlog2(n))
public static void main(String[] args) {
int arr [] = new int[1000000];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
long start = System.currentTimeMillis();
QuickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println((end - start)); //129毫秒
}
public static void QuickSort(int[] arr, int i, int j) {
int start = i;
int end = j;
if (start > end) {
return;
}
int baseNumber = arr[i];
while (start != end) {
while (true) {
if (end <= start || arr[end] < baseNumber) {
break;
}
end--;
}
while (true) {
if (end <= start || arr[start] > baseNumber) {
break;
}
start++;
}
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
QuickSort(arr, i, start - 1);
QuickSort(arr, start + 1, j);
}
最後就是快速排序了,跟名字一樣,确實很快。快排我沒有除1000,是以時間機關是毫秒,僅僅耗時129毫秒。多次測試,都不超過200毫秒。
結論:當基數不是很大時,幾種排序時間差距不是很大。冒泡和選擇在n較小時比較好,插入在大部分已排序時較好,快排在n較大時比較好。
由于是随機生成的數字,是以誤差肯定是有的,大家看一下就好,圖個樂子。