入門級算法-線性查找-時間複雜度O(n)--相當于算法界中的HelloWorld
二分查找(又稱折半查找) - 适用于已排好序的線性結構 - 時間複雜度O(logN)
冒泡排序 -- 時間複雜度O(n^2)
選擇排序 -- 時間複雜度O(n^2)
插入排序 -- 時間複雜度O(n^2)
字元串反轉 -- 時間複雜度O(logN)
關于穩定性排序的一個結論：
基于比較的簡單排序算法，即時間複雜度為O(N^2)的排序算法，通常可認為均是穩定排序
其它先進的排序算法，比如歸并排序、堆排序、桶排序之類（通常這類算法的時間複雜度可優化為n*LogN），通常可認為均是不穩定排序
單連結清單實作
-----------------------------
關于鄰接矩陣、鄰接表的選擇：
鄰接矩陣、鄰接表都是圖的基本存儲方式，
稀松圖情況下（即邊遠小于頂點情況下），用鄰接表存儲比較适合（相對矩陣N*N而言，鄰接表隻存儲有值的邊、頂點，不存儲空值，存儲效率更高）
稠密圖情況下（即邊遠大地頂點情況下），用鄰接矩陣存儲比較适合（資料較多的情況下，要對較做周遊，如果用連結清單存儲，要經常跳來跳去，效率較低）
-----------------------
堆：
幾乎完全的二叉樹：除了最右邊位置上的一個或幾個葉子可能缺少的二叉樹。在實體存儲上，可以用數組來存儲，如果A[j]的頂點有左、右子節點，則左節點為A[2j]、右節點為A[2j+1]，A[j]的父頂點存儲在A[j/2]中
堆：本身是一顆幾乎完全的二叉樹，而且父節點的值不小于子節點的值。應用場景：優先隊列，尋找最大或次最大值；以及把一個新元素插入優先隊列。
注：以下所有讨論的堆，約定索引0處的元素僅占位，有效元素從下标1開始
根據堆的定義，可以用以下代碼測試一個數組是否為堆：
節點向上調整siftUp
某些情況下，如果堆中的某個元素值改變後(比如 10,8,9,7 變成 10,8,9,20 後，20需要向上調整 )，不再滿足堆的定義，需要向上調整時，可以用以下代碼實作
節點向下調整siftDown (既然有向上調整，自然也有向下調整)
向堆中添加新元素
從堆中删除元素
堆排序：
這是一種思路非常巧妙的排序算法，精華在于充分利用了“堆”這種資料結構本身的特點（首元素必然最大），而且每個元素的上移、下調，時間複試度又比較低，僅為O(logN)，空間上，也無需借助額外的存儲空間，僅在數組自身内部交換元素即可。
思路：
1、先将首元素(即最大元素)與最末尾的元素對調---目的在于，把最大值沉底，下一輪重就不再管它了
2、經過1後，剩下的元素通常已經不再是一個堆了。這時，隻要把新的首元素用siftDown下調，調整完以後，新的最大值元素自然又上升到了首元素的位置
3、反複1、2，大的元素逐一沉底，最後整個數組就有序了。
時間複雜度分析：建立堆需要O(n)的代價，每次siftDown代價為O(logN)，最多調整n-1個元素，是以總代價為 O(N) + (N-1)O(logN)，最終時間複雜度為O(NLogN)
關于建堆，如果明白其中的原理後，也可以逆向思路，反過來做
--------------------------
不相交集合查找、合并
歸納法：
先來看二個排序的遞歸實作
遞歸的程式通常易于了解，代碼也容易實作，再來看二個小例子：
從數組中，找出最大值
有一個已經升序排序好的數組，檢查數組中是否存在二個數，它們的和正好為x ？
遞歸程式雖然思路清晰，但通常效率不高，一般來講，遞歸實作，都可以改寫成非遞歸實作，上面的代碼也可以寫成：
遞歸并不總代表低效率，有些場景中，遞歸的效率反而更高，比如計算x的m次幂，正常算法，需要m次乘法運算，下面的算法，卻将時間複雜度降到了O(logn)
當然，這其中并不光是遞歸的功勞，其效率的改進 主要依賴于一個數學常識： x^m = [x^(m/2)]^2，關于這個問題，還有一個思路很獨特的非遞歸解法，巧妙的利用了二進制的特點
再來看看經典的多項式求值問題：
給定一串實數An，An-1，...，A1，A0 和一個實數X，計算多項式Pn(x)的值
著名的Horner公式：
已經如何計算：
顯然有：
這樣隻需要 N次乘法+N次加法
多數問題：
一個元素個數為n的數組，希望快速找出其中大于出現次數>n/2的元素（該元素也稱為多數元素）。通常可用于選票系統，快速判定某個候選人的票數是否過半。最優算法如下：
以上算法基于這樣一個結論：在原序列中去除兩個不同的元素後，那麼在原序列中的多數元素在新序列中還是多數元素
證明如下：
如果原序列的元素個數為n，多數元素出現的次數為x，則 x/n > 1/2
去掉二個不同的元素後，
a)如果去掉的元素中不包括多數元素，則新序列中 ，原先的多數元素個數/新序列元素總數 = x/(n-2) ，因為x/n > 1/2 ，是以 x/(n-2) 也必然>1/2
b)如果去掉的元素中包含多數元素，則新序列中 ，原先的多數元素個數/新序列元素總數 = (x-1)/(n-2) ，因為x/n > 1/2 =》 x>n/2 代入 (x-1)/(n-2) 中，
有 (x-1)/(n-2) > (n/2 -1)/(n-2) = 2(n-2)/(n-2) = 1/2
下一個問題：全排列
------------------------
分治法：
要點：将問題劃分成二個子問題時，盡量讓子問題的規模大緻相等。這樣才能最大程度的展現一分為二，将問題規模以對數折半縮小的優勢。
split算法的思想應用：
設A[1..n]是一個整數集，給出一算法重排數組A中元素，使得所有的負整數放到所有非負整數的左邊，你的算法的運作時間應當為Θ(n)
未完待續...