偶然之下看到了
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
如果沒有交換數字的情況發生
代表整個陣列是從小排到大, -> 就不用排了
就會結束整個比較數字大小與交換數字的流程, 避免不必要的迴圈
