Java冒泡排序的詳細介紹（程式碼範例）

這篇文章帶給大家的內容是關於Java冒泡排序的詳細介紹（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

1、 導言

因為這是排序演算法系列的第一篇文章，所以多囉嗦幾句。

排序是很常見的演算法之一，現在很多程式語言都整合了一些排序演算法，像是Java 的Arrays.sort()方法，這種方式讓我們可以不在乎內部實作細節而直接調用，在實際的軟體開發當中也會經常使用到。但是站在開發者的角度而言，知其然必須知其所以然。多練練排序演算法，不僅能夠讓我們知道一些排序方法的底層實作細節，更能夠鍛鍊我們的思維，提升程式設計能力。現在很多技術面試也會牽涉到基本的排序演算法，所以多練習是有好處的。 （推薦：Java影片教學）

文中涉及到的程式碼都是Java實現的，但是不會涉及太多的Java語言特性，而且我會加上詳細的註釋，幫助你理解程式碼並且轉換成你熟悉的程式語言。

常見的排序演算法有以下10種：

• 冒泡排序、選擇排序、插入排序，平均時間複雜度都是O(n² )
• 希爾排序、歸併排序、快速排序、堆排序，平均時間複雜度都是O(nlogn)
• 計數排序、基數排序、桶排序，平均時間複雜度都是O(n k)

在開始具體的排序演算法講解之前，先得明白兩個概念：

##原地排序：指的是排序的過程當中不會佔用額外的儲存空間，空間複雜度為O(1)。
1. 排序演算法的穩定性：一個穩定的排序，指的是排序之後，相同元素的前後順序不會被改變，反之稱為不穩定。舉個例子：一個陣列[3，5，1，4，9，6，
2. 6，12] 有兩個6（為了區分，我把其中一個6 加粗），如果排序之後是這樣的：[1，3，4，5，6，6，9，12]（加粗的6 仍然在前面），就說明這是一個穩定的排序演算法。

2. 言歸正傳

冒泡排序的想法其實很簡單，一個資料跟它相鄰的資料進行大小的比較，如果滿足大小關係，就將這兩個資料交換位置。一直重複這個操作，就能將資料排序。

舉個例子，假如有數組a[3,5,1,4,9,6]，第一次冒泡的操作如下圖所示：

#重複進行這個動作，6次冒泡之後，資料排序完成。

根據這個思路，應該能很容易能夠寫出下面的程式碼實現冒泡排序：

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

但是這個排序演算法還可以進行最佳化，當冒泡操作已經沒有資料交換的時候，說明排序已經完成，就不用在進行冒泡操作了。例如上面的例子，第一次冒泡之後，數據為[3,1,4,5,6,9]，再進行一次冒泡，數據變為[1,3,4,5,6,9] ，此時已經完成了排序，就可以結束循環了。

所以針對這個陣列的排序，上面的程式碼需要6次冒泡才能完成，其中有4次都是不需要的。所以可以對程式碼進行最佳化：

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

好了，冒泡排序的基本想法和程式碼都已經實現，最後總結一下：

冒泡排序是基於資料比較的
1. 最好情況時間複雜度是O(n)，最壞情況時間複雜度是O(n
2. 2^{)，平均時間複雜度是O(n}2⁾
冒泡排序是原地排序演算法，並且是穩定的。

以上是Java冒泡排序的詳細介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！