冒泡排序–時間復雜度n^2
- 對數組序列從前向后依次比較相鄰兩個元素的大小,若逆序則兩個元素交換位置
- 如果一趟下來沒有發生交換,則說明序列有序,可以在序列中設置一個標志flag判斷元素是否發生交換,從而來減少不必要的比較(在寫完排序算法后再寫)
- 小結:
- 一共進行數組大小-1次的外部循環
- 每一趟排序的次數在逐漸地減少
- 在一趟排序中,沒有發生一次交換,則可以提前結束冒泡排序
- 第一趟排序,將最大的數排在最后,第2趟把第二大的數排在倒數第二個
演變過程:
int arr[]={3,9,-1,10,-2};
第1次排序結果[3, -1, 9, -2, 10]
第2次排序結果[-1, 3, -2, 9, 10]
第3次排序結果[-1, -2, 3, 9, 10]
第4次排序結果[-2, -1, 3, 9, 10]代碼實現:
import java.util.Arrays;
public class BubbleSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, -2};//第一趟排序,將最大的數排在最后int temp = 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]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第" + (i+1) + "次排序結果" + Arrays.toString(arr));}}
}優化:在排序循環完成之前就已經有序了,使用標志flag
優化之前:
int arr[] = {3, 9, -1, 10, 20};
第1次排序結果[3, -1, 9, 10, 20]
第2次排序結果[-1, 3, 9, 10, 20]
第3次排序結果[-1, 3, 9, 10, 20]
第4次排序結果[-1, 3, 9, 10, 20]優化之后:
int arr[] = {3, 9, -1, 10, 20};
第1次排序結果[3, -1, 9, 10, 20]
第2次排序結果[-1, 3, 9, 10, 20]
實現代碼:
在每一次排序完后,進行判斷是否有過交換
import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, 20};boolean flag = false;//標志變量,表示是否進行過交換//第一趟排序,將最大的數排在最后int temp = 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]) {flag=true;//交換過temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag){//在一趟排序中,一次交換都沒有發生過break;}else {flag=false;//重置flag,進行下一次交換}System.out.println("第" + (i + 1) + "次排序結果" + Arrays.toString(arr));}}
}時間測試:
實現思路:
//測試時間Date date2 = new Date();//格式化時間SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String dateStr2 = simpleDateFormat2.format(date2);System.out.println("排序后的時間: " + dateStr2);
排序前的時間: 2020-12-09 16:43:12
排序后的時間: 2020-12-09 16:43:22
代碼實現:
import java.text.SimpleDateFormat;
import java.util.Date;public class BubbleSort {public static void main(String[] args) {int arr[] = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 80000);//生成[0,80000)的隨機數}//測試時間Date date1 = new Date();//格式化時間SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String dateStr = simpleDateFormat.format(date1);System.out.println("排序前的時間: " + dateStr);boolean flag = false;//標志變量,表示是否進行過交換//第一趟排序,將最大的數排在最后int temp = 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]) {flag = true;//交換過temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag) {//在一趟排序中,一次交換都沒有發生過break;} else {flag = false;//重置flag,進行下一次交換}}//測試時間Date date2 = new Date();//格式化時間SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String dateStr2 = simpleDateFormat2.format(date2);System.out.println("排序后的時間: " + dateStr2);}
}參考B站尚硅谷視頻–冒泡排序
