冒泡排序以及如何優化冒泡排序

冒泡排序：

冒泡排序的基本思想是：通過對待排序序列從前往後（從下标較小的元素開始），

依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向後部，就像水底下的泡泡一樣逐漸向上冒。

測試八萬個資料進行排序，使用優化後的代碼大緻需要20秒

代碼如下：

public static void bubbleSort(int[] arr){
       int temp=0;
       for (int i = 0; i < arr.length-1; i++) {
           for (int j = 0; j < arr.length-1; j++) {
               //如果前面的數比後面的大，則交換
               if(arr[j]>arr[j+1]){
                   temp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=temp;
               }
           }
       }
       return arr;
}
           

如何優化冒泡排序？

我們可以在第一層循環中，定義一個boolean類型的辨別變量，用于判斷目前循環是否進行過交換，如果沒有進行過交換，則可以提前結束循環，表示排序已經結束

代碼如下：

public static void bubbleSort(int[] arr){
        int temp=0;
        boolean flag=false;//辨別變量，表示是否進行過交換
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1; 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;
            }
        }
        return arr;
}