Bubble Sort 氣泡演算法 Java實作

偶然之下看到了

http://www.mkyong.com/java/java-bubble-sort-example/

想說自己也從0開始寫一個試試看

目標:

氣泡排序法基本上就是給你一串陣列

比如說 1597253 , 要排成 1235579

第一個數字跟第二個數字比較, 左邊比較大就跟右邊換位, 沒的話就不用動

以此類推往右比到最後, 此時最後一個數字肯定最大

如果第一輪比完陣列變成遞增排序了, 那就結束

沒比完從左邊再開始比一次,

當然第二輪就不用比到最後一個數字, 因為最後一個數字已經是最大了

以此類推比到整個陣列變成遞增排序

我自己的思考流程如下....

 

Step1.

從 0 開始想了這麼一個實作...

public class BubbleSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] test = new int[]{2, 1, 3, 2, 5, 4};
		
		int[] a= sort(test);
		for(int t:a){
			System.out.print(t);
		}

	}


    static int[] sort(int[] input){
		
		int length = input.length;//要排列的數字長度
	    int temp;//前面數字>後面數字時兩個會互換位置,此時需要此變數
	    
        //每個數字都要比對
	    for(int i=0;i<length;i++){
	    	
	    	for(int j=0;j<length-1;j++){
	    	   
	    	   //比大小,if 前>後 換位
	    	   if(input[j]>input[j+1]){
	    		   
	    		  temp = input[j];//前面數字先存到變數
	    		  input[j] = input[j+1];//後面數字取代前面數字
	    		  input[j+1] = temp; //將變數(前面數字)存到後面變數
	    		
	    	   }

	    	}
	    	
	    }
		return input;
     }

}

 

測試結果:

122345  , 正確

 

 

Step2.

比較前後數字大小次數 + 交換前後數字次數有多少 

以及印出比較前與交換數字前的陣列對照

static int[] sort(int[] input){
		
		int count = 0;
		int length = input.length;
	    int temp;
	    
	    for(int i=0;i<length;i++){    	
	    	
	    	for(int j=0;j<length-1;j++){
	    	   
	    	   //比大小,前>後 換位
	    	   if(input[j]>input[j+1]){
	    		   
	    		  temp = input[j];
	    		  input[j] = input[j+1];
	    		  input[j+1] = temp; 
	    		  count++;
	    		  
		    	  //這裡印出比較+換位的次數bigin
		    	  System.out.print("count:" + count + " ");
		          for(int a:input){
		    	    System.out.print(a);
		    	  }
		    	  System.out.println();
		    	  //end 
	    		  
	    	   }

	    	}
	    	
	    }
		System.out.println(count);
		return input;
	}

Output為...

count:1 123254 
count:2 122354
count:3 122345
3

3  = 交換前後次數:

這會依據數字排列的情況改變, 本例只有三次

如果帶賽是 543221

那就是每次比較完都要交換數字, 所以是 5 + 4 + 3 + 2 + 1 = 15

 

比較前後數字次數:

每一次都要比, 設總共有 n 個數字, 那麼第一次整排比完就是 n -1 

下一次比較因為最大的數字跑到最右邊了, 所以少了一個比較的次數就是 n-2, 以此類推

(n-1) + (n-2) + ..+ 2 + 1 =  (1 + ( n -1 )) x (n -1) / 2   = n ( n - 1 ) / 2 

本例的比較次數就是這個迴圈執行的次數

for(int j=0;j<length-1;j++)

所以是 5  +  4 + 3 + 2 + 1 = 15  

 

 

Step3.

看了下範例, 發現有

boolean is_sorted;

這個變數, 

看了下使用時的註解..

 // is sorted? then break it, avoid useless loop.
            if (is_sorted) break;

實際上使用是這樣

static int[] sort(int[] input){
		
		int count = 0;
		int length = input.length;
	    int temp;
	    Boolean is_sorted;//用來判斷數字需不需要互換位置的flag
	    
	    for(int i=0;i<length;i++){
	    	
	    	is_sorted = true;
	    	
	    	for(int j=0;j<length-1;j++){
	    	   
	    	   //比大小,前>後 換位
	    	   if(input[j]>input[j+1]){
	    		   
	    		  temp = input[j];
	    		  input[j] = input[j+1];
	    		  input[j+1] = temp; 
	    		  count++;
	    		  
		    	  //這裡印出比較+換位的次數bigin
		    	  System.out.print("count:" + count + " ");
		          for(int a:input){
		    	    System.out.print(a);
		    	  }
		    	  System.out.println();
		    	  //end 
	    		  
	    		  is_sorted = false;
	    	   }

	    	}
	    	//System.out.println(is_sorted);
	    	if (is_sorted) break;//如果一個一個數比較完畢,都沒有出現前面大於後面的情況,直接結束整個判斷
	    	
	    }
		System.out.println(count);
		return input;
	}

這個 flag 只要在交換數字後就會設定為 false

如果沒有交換數字的情況發生

代表整個陣列是從小排到大, -> 就不用排了

就會結束整個比較數字大小與交換數字的流程, 避免不必要的迴圈