Java：氣泡排序 | 二分查詢
摘要：
2018-10-29 20:16:46
氣泡排序
例子（對數字排序）：
假設有這樣一組數字：32， 8， 128， 2， 64
現在對其進行氣泡排序（*表示下次比較的開始數字）：
32>8？ ture： 將32和8調換位置 8， 32*， 128， ...
2018-10-29 20:16:46
氣泡排序
例子（對數字排序）：
假設有這樣一組數字：32， 8， 128， 2， 64
現在對其進行氣泡排序（*表示下次比較的開始數字）：
32>8？ ture： 將32和8調換位置 8， 32*， 128， 2， 64；
32>128？ false：保持原位置不動 8， 32， 128*， 2， 64；
128>2 ？ true： 將128和2調換位置 8， 32， 2， 128*， 64；
128>64 ？ true：將128和64調換位置 8， 32， 2， 64， 128*；
經過以上步驟，最大數128浮出水面。
現在找出剩餘數字 8， 32， 2， 64 中的最大數：
8>32？ false： 保持原位置不動 8， 32*， 2， 64；
32>2 ？ ture： 將32和2調換位置 8， 2， 32*， 64；
32>64？ false： 保持原位置不動 8， 2， 32， 64*；
經過以上步驟，最大數64浮出水面。
...
由此一步步比較，即可得到排序後的結果：2， 8， 32， 64， 128
程式實現如下：
//形式引數intArr表示要排序的陣列
1public static int[] bubbleSort(int[] intArr) {
2if (intArr == null)
3return null; // 當傳進來的陣列為null時返回null
4int len = intArr.length; // 定義len表示陣列的長度
5if (len < 2)
6return intArr; // 當陣列長度小於2時直接返回該陣列，此時無需排序
7
8while (len > 1) {
9for (int i = 0; i < len - 1; i++) {
10// if語句表示如果前一個數大於後一個數，則交換位置，否則什麼也不做
11if (intArr[i] > intArr[i + 1]) {
12int temp = intArr[i];
13intArr[i] = intArr[i + 1];
14intArr[i + 1] = temp;
15}
16}
17len -= 1; // 經過一個迴圈的比較，已經得出了本次迴圈的最大值，把它放在索引最大處，接下來比較除最大索引處之外的數的最大值，依次迴圈...
18}
19return intArr;
20}
二分查詢
例子（對上述排序好的數字進行查詢）：
有如下排序好的數字：2， 8， 32， 64， 128
索引值分別為 0， 1， 2， 3， 4
如何查詢數字 2 的索引呢？
取中間索引 2 處的值 32 ， 32<2 ？ false，說明數值2的索引在索引2的前面；
取索引0和索引2的中間索引值1，索引1處的值為8， 8<2 ？ false，說明數值2的索引在索引1的前面；
...
依次取值比較即可得到數值2的索引為1；
程式實現如下：
引數表示在陣列intArr中查詢值value所在的索引
1public static int binarySearch(int value, int[] intArr) {
2int low = 0; // low表示最小索引
3int high = intArr.length - 1; // len表示最大索引
4
5while (high >= low) {
6// 0 1 2 3 4 5 中間索引指2;
7// 0 1 2 3 4 中間索引則為2
8int mid = (low+high) >>> 1; // mid表示len無符號右移一位，最高位補0，即除以2
9int midVal = intArr[mid]; // midVal表示陣列中間索引處值
10
11if (midVal < value)
12low = mid + 1;
13else if (midVal > value)
14high = mid - 1;
15else
16return mid; // 當要查詢的值找到時返回其索引
17}
18return -1; // 當要查詢的值未找到時返回-1
19}