排序–冒泡排序
- 2019 年 10 月 20 日
- 筆記
1、什麼是冒泡排序?
就是把一個無序數組內的元素，從頭開始，兩兩比較並交換位置，直到把最大（最小）的一位放置在隊尾
2、程式碼原理：
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
- 針對所有的元素重複以上的步驟，除了最後一個；
- 重複步驟1~3，直到排序完成。
3、程式碼實現
public class ArrSort { public static void main(String[] args) { int[] arr={3,9,-1,10,20}; int temp=0; for (int j=0;j<arr.length-1;j++){ //第i遍 for (int i=0;i<arr.length-1-j;i++){ if (arr[i]>arr[i+1]){ //左邊元素比右邊大就交換位置 temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } System.out.println("第"+j+"次排序"); System.out.println(Arrays.toString(arr)); } } }
4、優化
按照上述的程式碼，每次排序都要進行arr.length-1輪，但是有可能前面幾輪就已經達到排序好的效果，後面做的就是無用功
如圖第二輪已經達到排序完成的效果，怎麼優化？
加一個判定條件，如果沒有發生元素的交換，就說明已經排序完成了
public class ArrSort { public static void main(String[] args) { int[] arr={3,9,-1,10,20}; int temp=0; //設置一個開關 boolean flag=false; for (int j=0;j<arr.length-1;j++){ //第一遍 for (int i=0;i<arr.length-1-j;i++){ if (arr[i]>arr[i+1]){ //發生元素交換就置為true，這一輪完成後再判斷 flag=true; temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } if (flag){ //說明發生了元素交換，繼續進行下一輪 System.out.println("第"+j+"次排序"); System.out.println(Arrays.toString(arr)); flag=false; //再把flag置為初始值 }else{ //沒有進行元素交換，就跳出循環條件，排序完成 System.out.println("排序結束"); break; } } } }
5、時間複雜度
由上述程式碼可發現，冒泡排序是用了雙層for循環，所以O（n^2）
