冒泡排序
第一，冒泡排序是原地排序演算法嗎?
冒泡的程序只涉及相鄰資料的交換操作，只需要常量級的臨時空間，所以它的空間復雜度為 O(1)，是一個原地排序演算法，
第二，冒泡排序是穩定的排序演算法嗎?
在冒泡排序中，只有交換才可以改變兩個元素的前后順序，為了保證冒泡排序演算法的穩定
性，當有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的資料在排序前后不會
改變順序，所以冒泡排序是穩定的排序演算法，
第三，冒泡排序的時間復雜度是多少?
最好情況下，要排序的資料已經是有序的了，我們只需要進行一次冒泡操作，就可以結束 了，所以最好情況時間復雜度是 O(n)，而最壞的情況是，要排序的資料剛好是倒序
排列 的，我們需要進行 n 次冒泡操作，所以最壞情況時間復雜度為 O(n2)，
冒泡排序優化(沒有交換，提前退出)
// 冒泡排序，a 表示陣列，n 表示陣列大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡回圈的標志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交換 int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有資料交換 }
}
if (!flag) break; // 沒有資料交換，提前退出
}
}
遞回
遞回需要滿足的三個條件：
1. 一個問題的解可以分解為幾個子問題的解，何為子問題?子問題就是資料規模更小的問題，
2. 這個問題與分解之后的子問題，除了資料規模不同，求解思路完全一樣
3. 存在遞回終止條件：把問題分解為子問題，把子問題再分解為子子問題，一層一層分解下去，不能存在無限回圈，這就需要有終止條件，
基本公式
f(n) = f(n-1)+f(n-2)
遞回代碼要警惕重復計算
除此之外，使用遞回時還會出現重復計算的問題，例如 f(6) = f(5) + f(4) , f(7) = f(6) + f(5) , 可以看到計算f(6) 和 f(7) 的時候，明顯的重復計算了f(5)，
public int f(int n) { if (n == 1) return 1; if (n == 2) return 2; // hasSolvedList 可以理解成一個 Map，key 是 n，value 是 f(n) if (hasSolvedList.containsKey(n)) { return hasSovledList.get(n); } int ret = f(n-1) + f(n-2); hasSovledList.put(n, ret); return ret; }
遞回還有很多其他問題，例如在時間效率上，遞回代碼里多了很多函式呼叫，當這些函式呼叫的數量較大時，就會積聚成 一個可觀的時間成本，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/218798.html
標籤：其他
上一篇：大型專案工程代碼快速上手指北
下一篇：TCP擁塞控制原理