java排序算法之冒泡排序

冒泡排序是java十大排序算法中的基礎算法，了解其實作原理很有必要，下面就來說說冒泡排序，其實作代碼并不複雜，主要是弄清楚執行的流程，

一、基本概念：

依次比較相鄰的兩個數，将小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，将小數放前，大數放後。然後比較第2個數和第3個數，将小數放前，大數放後，如此繼續，直至比較最後兩個數，将小數放前，大數放後。至此第一趟結束，将最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），将小數放前，大數放後，一直比較到倒數第二個數（倒數第一位置上已經是最大的），第二趟結束，在倒數第二位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重複以上過程，直至最終完成排序。

二、實作思路：

用二重循環實作，外循環變量設為i，内循環變量設為j。假如有n個數需要進行排序，則外循環重複n-1次，内循環依次重複n-1，n-2，…，1次。每次進行比較的兩個元素都是與内循環j有關的，它們可以分别用a[j]和a[j+1]辨別，i的值依次為1,2,…,n-1，對于每一個i，j的值依次為0,1,2,…n-i 。

設數組長度為N：

1．比較相鄰的前後二個資料，如果前面資料大于後面的資料，就将二個資料交換。

2．這樣對數組的第0個資料到N-1個資料進行一次周遊後，最大的一個資料就“沉”到數組第N-1個位置。

3．N=N-1，如果N不為0就重複前面二步，否則排序完成。

三、java代碼實作：

運作主函數，可以看到已經對測試的數組中的資料進行了排序，

四、性能分析：

若記錄序列的初始狀态為"正序"，則冒泡排序過程隻需一趟排序，此過程最簡單也是最好的一種情況，時間複雜度為O(n)；反之，若記錄序列的初始狀态為"逆序"，則需進行n(n-1）/2次比較和記錄移動。是以冒泡排序總的時間複雜度為O(nn)。總體來看，冒泡排序的平均書劍複雜度為O(nn)