對于冒泡排序,時間復雜度是O(n^2),所以可見,在n比較小的場景下,它的效率明顯是更高的
我們還可以通過一個boolean值,來判斷在這次回圈中,有沒有變數被更換位置,如果沒有,說明后面的順序都已經調整好,可以直接跳出回圈.可以減少回圈次數(效率有限)
拓展:在Hadoop的MapReduce任務中,我們是使用到了一次快排和兩次歸并排序,這兩種排序對于大體量的排序效果較好(后期會寫).快排對于全域無序的效率更高;歸并對于磁區內有序,磁區間無序的效率更高.
整體代碼
import java.util.Arrays;
import java.util.Random;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{6,9,-7,3,2,8};
sort(arr);
//測驗一下,假如說有一個8w長度的陣列
int[] arr1 = new int[80000];
Random random = new Random();
for (int i = 0; i < arr1.length; i++) {
arr1[i] = random.nextInt(80000);
}
long start = System.currentTimeMillis();
sort(arr1);
long end = System.currentTimeMillis();
System.out.println((end - start) / 1000);
/*第一次遍歷,要把最大的放到最后面
int tmp = 0;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i+1]){
tmp = arr[i+1];
arr[i + 1] = arr[i];
arr[i] = tmp;
}
}*/
//原冒泡排序
/*int tmp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){
tmp = arr[j+1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}*/
}
public static void sort(int[] arr){
//優化冒泡排序
int count = 0;
int tmp = 0;
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]){
flag = true;
tmp = arr[j+1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
count++;
if (!flag){
break;
}
}
System.out.println("經歷了" + count +" 次排序后"+ Arrays.toString(arr));
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/377003.html
標籤：其他
上一篇：[ElasticSearch系列五] Spring Data Elasticsearch 物體類注解說明【專攻系】
下一篇：Hadoop筆記（偽分布事搭建）