Java冒泡排序

排序算法概述

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。

穩定性：一個排序算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。

如果算法是穩定的有什么好處呢？排序算法如果是穩定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。

排序算法根據是否需要訪問外存分為內部排序和外部排序。

內部排序是指待排序列完全存放在內存中所進行的排序過程，適合不太大的元素序列。

外部排序指的是大文件的排序，即待排序的記錄存儲在外存儲器上，待排序的文件無法一次裝入內存，需要在內存和外部存儲器之間進行多次數據交換，以達到排序整個文件的目的。

我們現在要討論的排序都是內部排序。

冒泡排序

冒泡排序的效率很低，但是算法實現起來很簡單，因此很適合作為研究排序的入門算法。

基本思想

對當前還未排好序的范圍內的全部數，自上而下對相鄰的倆個數依次進行比較和調整，讓較大的數下沉，較小的數往上冒。即：每當倆相鄰的數比較后發現他們的排序與排序的要求相反時，就將他們交換。每次遍歷都可確定一個最大值放到待排數組的末尾，下次遍歷，對該最大值以及它之后的元素不再排序(已經排好)。

java實現

public class Sort{ private int [] array; public Sort(int [] array){ this.array = array; } //按順序打印數組中的元素 public void display(){ for(int i=0;iarray[j]){ //如果前一位大于后一位，交換位置 temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; } } System.out.print("第"+(i+1)+"輪排序結果："); display(); } } }

測試：

public static void main(String[] args) { int [] a = {1,5,4,11,2,20,18}; Sort sort = new Sort(a); System.out.print("未排序時的結果："); sort.display(); sort.bubbleSort(); }

打印結果：

算法分析

上面的例子中，待排數組中一共有7個數，第一輪排序時進行了6次比較，第二輪排序時進行了5比較，依次類推，最后一輪進行了一次比較。加入元素總數為N，則一共需要的比較次數為：

(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2

這樣，算法約做了N2/2次比較。因為只有在前面的元素比后面的元素大時才交換數據，所以交換的次數少于比較的次數。如果數據是隨機的，大概有一半數據需要交換，則交換的次數為N2/4(不過在最壞情況下，即初始數據逆序時，每次比較都需要交換)。

交換和比較的操作次數都與N2成正比，由于在大O表示法中，常數忽略不計，冒泡排序的時間復雜度為O(N2)。O(N2)的時間復雜度是一個比較糟糕的結果，尤其在數據量很大的情況下。所以冒泡排序通常不會用于實際應用。

冒泡排序的改進

上面已經分析過，冒泡排序的效率比較低，所以我們要通過各種方法改進。

最簡單的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程.

在上例中，第四輪排序之后實際上整個數組已經是有序的了，最后兩輪的比較沒必要進行。

改進后的代碼如下：

//冒泡排序改進1 public void bubbleSort_improvement_1(){ int temp; int len = array.length; for(int i=0;iarray[j]){ //如果前一位大于后一位，交換位置 temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; if(!exchange) exchange =true; //發生了交換操作 } } System.out.print("第"+(i+1)+"輪排序結果："); display(); if(!exchange) break; //如果上一輪沒有發生交換數據，證明已經是有序的了，結束排序 } }

用同樣的初始數組測試，打印結果如下：

上面的改進方法，是根據上一輪排序有沒有發生數據交換作為標識，進一步思考，如果上一輪排序中，只有后一段的幾個元素沒有發生數據交換，是不是可以判定這一段不用在進行比較了呢？答案是肯定的。

例如上面的例子中，前四輪的排序結果為：

未排序時的結果：1 5 4 11 2 20 18第1輪排序結果：1 4 5 2 11 18 20第2輪排序結果：1 4 2 5 11 18 20第3輪排序結果：1 2 4 5 11 18 20第4輪排序結果：1 2 4 5 11 18 20

第1輪排序之后，11、18、20已經是有序的了，后面的幾次排序后它們的位置都沒有變化，但是根據冒泡算法，18依然會在第2輪參與比較，11依然會在第2輪、第3輪參與比較，其實都是無用功。

我們可以對算法進一步改進：設置一個pos指針，pos后面的數據在上一輪排序中沒有發生交換，下一輪排序時，就對pos之后的數據不再比較。

代碼改動如下：

//冒泡排序改進2 public void bubbleSort_improvement_2(){ int temp; int counter = 1; int endPoint = array.length-1; //endPoint代表最后一個需要比較的元素下標 while(endPoint>0){ intpos = 1; for(int j=1;j<=endPoint;j++){ if(array[j-1]>array[j]){ //如果前一位大于后一位，交換位置 temp= array[j-1]; array[j-1]= array[j]; array[j]= temp; pos= j; //下標為j的元素與下標為j-1的元素發生了數據交換 } } //下一輪排序時只對下標小于pos的元素排序，下標大于等于pos的元素已經排好 endPoint= pos-1; System.out.print("第"+counter+"輪排序結果："); display(); } }

對的算法來說，沒有最好，只有更好。上面的兩種改進方法其實治標不治本，是一種“揚湯止沸”的改進，下面我們來一次“釜底抽薪”的改進。

傳統的冒泡算法每次排序只確定了最大值，我們可以在每次循環之中進行正反兩次冒泡，分別找到最大值和最小值，如此可使排序的輪數減少一半。

改進代碼如下：

//冒泡排序改進3 public void bubbleSort_improvement_3(){ int temp; int low = 0; int high = array.length-1; int counter = 1; while(lowarray[i+1]){ //如果前一位大于后一位，交換位置 temp= array[i]; array[i]= array[i+1]; array[i+1]= temp; } } --high; for(int j=high;j>low;--j){ //反向冒泡，確定最小值 if(array[j]

如果有興趣和我們一起討論問題的話，不妨加下我們群吧 ，記得加群的時候寫上我名字 ID：BigMoreKT：984370849

總結

以上是生活随笔為你收集整理的java 冒泡排序_Java冒泡排序详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。