算法排序之鄰居好說話--冒泡排序(Bubble Sort)

冒泡排序(Bubble Sort)：是非常容易了解和實作的，主要思想是每次比較兩個相鄰的元素，如果他們的順序錯誤就把他們交換過來。

以從大到下排序為例，

設随機生成1000範圍内的n個數。

1. 比較相鄰的前後兩個數，如果前面的數小于了後面的數，就将後面的數交換。

2. 對随機生成數組的0到n-1資料周遊一遍後，最小的一個數就歸位到數組第n-1處，即最後一個位置。

3. 重複前面第二步，直到最後一個尚未歸位的數，已經歸位的數則無須再進行比較。

按以上描述很容易寫出的java代碼如下：

public static void main(String[] args) {
		
		long startTime = System.currentTimeMillis();
		bubbleSort(1000);
		long endTime = System.currentTimeMillis();
		System.out.println("\n" + (endTime - startTime));
	}
	
	public static void bubbleSort(Integer n) {
		
		Random r = new Random();
		int[] num = new int[n];
		for (int i = 0; i < n; i++) {
			num[i] = r.nextInt(10000);
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 1; j < n-i; j++) {
				
				int temp = 0;
				if (num[j-1] < num[j]) {
					temp = num[j-1];
					num[j-1] = num[j];
					num[j] = temp;
				}
			}
		}
		
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
	}
           

冒泡排序的核心部分是雙重嵌套循環， 不難看出時間複雜度為O(N^2)。

這是一個非常高的時間複雜度，在資料規模很小時，可以采用，但當資料規模較大時，最好是用其它的排序方法。