class BubbleSort{
	
	private static int HOW_MANY_RANDOM_NUMBER = 200;
	private static int MAX_RANDOM_NUMBER = 1000;

	private static int swap(int n1, int n2){
		return n1;
	}

	private static void bubble(int data[]){
		int cursor=0, index=0;
		for(index=0; index<data.length; index++){
			for(cursor=0; cursor<data.length-index-1; cursor++){
				if(data[cursor] > data[cursor+1]){
					data[cursor+1]= swap(data[cursor], data[cursor]=data[cursor+1]);
				}
			}
		}
	}

	private static void printArray(int data[]){
		System.out.print("[data]: ");
		for(int x : data){
			System.out.print(x+ " ");
		}
		System.out.println();
	}

	private static int[] numberGenerator(int howmany, int howbig){
		int tmp[] = new int[howmany];
		for(int x=0; x<tmp.length; x++){
			tmp[x] = (int)(Math.random()*howbig+1);
		}
		return tmp;
	}

	public static void main(String args[]){
		System.out.println("現在要取"+HOW_MANY_RANDOM_NUMBER+"個 1~"
			+MAX_RANDOM_NUMBER+" 的亂數資料");
		// 取HOW_MANY_RANDOM_NUMBER個 1~MAX_RANDOM_NUMBER 的亂數存進去data陣列中
		int data[]= numberGenerator(HOW_MANY_RANDOM_NUMBER, MAX_RANDOM_NUMBER);
		// 顯示data內的排序
		printArray(data);
		System.out.println("資料經過Bubble Sort之後");
		// 把data用bubble排序過
		bubble(data);
		// 再顯示出來
		printArray(data);
	}
}

練習重點:

1. bubble sort的概念：

將一串數列由小到大排序，像在水中的泡泡一樣，小泡泡浮上去、大泡泡往後排

2. bubble sort的時間複雜度：

最佳時間：O(n)

平均時間：O(n^2)

最差時間：O(n^2)

空間複雜度：O(1) => 指所需要佔用的空間大小，O(1)表示佔用空間固定，不受數列大小影響

代表一串數列經過bubble sort之後，所花的時間，

最好的情況下就是一開始就排好了，不需要再排序，但還是要走過一輪把數列的每個都檢查過一次，所以跟數列的數量一樣(n)

最差的情況就是大小順序完全相反，每個都需要重新排一次，也就是把數列的每個元素(n)都檢查過n*n次

* 如何證明時間複雜度呢？

將數列數量逐漸增加，觀察所需排序時間：

3. java的random：

private static int[] numberGenerator(int howmany, int howbig){
		int tmp[] = new int[howmany];
		for(int x=0; x<tmp.length; x++){
			tmp[x] = (int)(Math.random()*howbig+1);
		}
		return tmp;
	}

4. java的swap：

private static int swap(int n1, int n2){
		return n1;
}

要把x和y交換
使用: data[cursor+1]= swap(data[cursor], data[cursor]=data[cursor+1]);
代數簡化版: y= swap(x,x=y);

 

參考：

1. 小殘的城市光廊：http://emn178.pixnet.net/blog/post/93779892-氣泡排序法(bubble-sort)