一、二分查找

? ? ? ? ?1、前提條件：數(shù)據(jù)有序，隨機訪問；

? ? ? ? ?2、實現(xiàn)：遞歸實現(xiàn)，非遞歸實現(xiàn)

? ? ? ? ?3、注意事項：

????????????????循環(huán)退出條件:low <=high,low = high.說明還有一個元素，該元素還要與key進行比較

? ? ? ? ? ? ? ? mid的取值：mid=（low + high）/2；mid = low + （（high - low）>>1)

? ? ? ? ? ? ? ? low 和high 的更新：low = mid +1；high = mid - 1；不能寫成low = mid +1，high = mid-1；又可能出現(xiàn)死循環(huán)；

? ? ? ? 代碼實現(xiàn)：

1、查找第一個與key相等的元素：

2、查找最后一個與key相等的元素

3、查找最后一個小于等于key值的元素

4、查找第一個大于等于key值的元素

二、冒泡排序

? ? ? ? 如何評價一個算法：

? ? ? ? 1、時間復(fù)雜度：最好情況；最壞情況；平均情況；系數(shù)和低階項

? ? ? ? 2、空間復(fù)雜度：原地排序（特指空間復(fù)雜度為O（1））的排序；

? ? ? ? 3、穩(wěn)定性：數(shù)據(jù)集中“相等”的元素，如果排序前和排序后的相對次序不變，那么這個排序就是穩(wěn)定的；

? ? ? ? 穩(wěn)定性就是排序算法的很重要的指標；

冒泡排序：

? ? ? ? 比較相鄰的元素，如果前一個比后一個大，就交換次序，

? ? ? ? 對每一對相鄰元素做同樣的工作，從第一對到最后一對。最大的元素就會位于最后位置；

? ? ? ? 除最后一個元素外，對其他元素重復(fù)上面的步驟，直到元素的個數(shù)為1；

時間復(fù)雜度：

? ? ? ? 最好情況原數(shù)組有序（O（n））；

? ? ? ? 最壞情況原數(shù)組逆序（比較次數(shù)（n-1）+(n-2)+...+1 = （n（n-1））/2）

? ? ? ? ???????????????????????????????????交換次數(shù)：（（n-1）+（n-2）+...+1? = （n（n-1））/2）

? ? ? ? 平均情況（每一種情況出現(xiàn)的情況是相等的）：總情況（N！）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （比較次數(shù)：大于交換的次數(shù)，小于（n（n-1））/2）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（交換次數(shù)（n（n-1）/4））

分析：有序元素對，逆序元素對，逆序度，有序度；

有序?qū)?#xff1a;34，24，14

逆序?qū)?#xff1a;12，13，23

排序的過程：增加有序度，減少逆序度，最終達到滿有序度；

冒泡排序交換導(dǎo)致有序度+1，逆序度-1；

空間復(fù)雜度：O（1）；//原地排序

穩(wěn)定性：穩(wěn)定，arr[j]>arr[j+1]? ?才發(fā)生交換；

三、選擇排序(無論什么數(shù)據(jù)進去都是（O（n2））的時間復(fù)雜度，所以用它的時候數(shù)據(jù)規(guī)模越小越好，唯一好處是不占用額外內(nèi)存)

? ? ? ? 工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再從剩余未排序中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾，以此類推，直到所有元素均排序完畢；（選擇排序不能像冒泡排序一樣去優(yōu)化）

? ? ? ? 時間復(fù)雜度：O(n2)

? ? ? ? ? ? ? ? 比較次數(shù)：（n-1）+ ...+1 =(n(n-1))/2

? ? ? ? ? ? ? ? 交換次數(shù)：n-1;

? ? ? ? 空間復(fù)雜度：O（1）原地排序

? ? ? ? 穩(wěn)定性：不穩(wěn)定，發(fā)生了長距離的交換；

四、插入排序：

? ? ? ? 工作原理：通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在從后向前掃描過程中，需要反復(fù)把已排序的元素逐步向后挪位，為最新元素提供插入空間；

? ? ? ? 時間復(fù)雜度：

? ? ? ? ? ? ? ? 最好情況：（O（n））

????????????????????????????????原數(shù)組有序(比較次數(shù)，（n-1）)交換次數(shù)：原數(shù)組有序（0）

? ? ? ? ? ? ? ? 最壞情況：（O（n2））

????????????????????????????????原數(shù)組逆序（比較次數(shù)，（n-1）+（n-2）+...+1 = (n(n-1))/2）;

交換次數(shù)（（n-1）+(n-2)+...+1 =(n(n-1))/2：

? ? ? ? ? ? ? ? 平均情況：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 比較次數(shù)：大于交換次數(shù)，小于（n（n-1））/2

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 交換次數(shù)：（n（n-1））/4（逆序個數(shù)）

插入排序好處，當(dāng)元素基本有序時，其性能非常好；

空間復(fù)雜度，O（1），原地排序

穩(wěn)定性：穩(wěn)定；

冒泡排序，選擇排序，插入排序小結(jié)：

????????

五、希爾排序（縮小增量排序，插入排序的改進版本）：

? ? ? ? 第一批打破O（n2）這個時間復(fù)雜度的方法；

? ? ? ? gap（希爾）：n/2、n/4、...1;

gap = n/2=5

????????

先按gap分組，組內(nèi)使用簡單的插入排序（十個元素分為5組）；

第一次組間排序完成后，就縮小增量，gap=5/2=2；gap =1；

時間復(fù)雜度比O（n2）小，和具體的gap序列相關(guān)；

空間復(fù)雜度O（1）原地排序；

穩(wěn)定性：不穩(wěn)定，會發(fā)生長距離交換；

六、歸并排序：

? ? ? ? 先把大數(shù)組分成兩個小數(shù)組，直到有序再合并；單個數(shù)組已經(jīng)算是有序的；

用遞歸解決；

????????

注意釋放堆區(qū)數(shù)組

????????

七、快速排序

? ? ? ? 從數(shù)列中挑出一個元素，稱為“基準”（pivot）；（一般情況下可以選幾個值取中位數(shù)，也可以選第一位，或者隨機位）

? ? ? ? 重新排序數(shù)列，所有元素比基準值小的拜訪在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任意邊。）在這個分區(qū)退出后，改基準就處于數(shù)列的中間位置（也就是最終位置）這個操作我們稱之為分區(qū)（partition）；

? ? ? ? 遞歸地把小于基準值元素地子數(shù)列和大于基準值元素地子數(shù)列排序（左右兩邊都使用快排）；

i 是放下一個比基準值小的位置，j放比基準值大的值；先移動 j 再移動 i ；

先找比基準值小的，再找比基準值大的，交替找直到? i? j 相遇，基準值的位置就確定了；

因為基準值已經(jīng)保存就可以移動 j 把第一個值覆蓋掉（以第一個值為基準）

時間復(fù)雜度：

? ? ? ? 最好情況：（每次分區(qū)都分成大小相等的兩份）

? ? ? ? 最壞情況：每次基準值都位于最左邊或者最右邊；

? ? ? ? 平均情況(假設(shè)每次分成三比一的情況)：

空間復(fù)雜度：

快速排序的改進策略（基準值的選取（隨機選，選擇多個元素的中位數(shù)）；分區(qū)操作的優(yōu)化；選擇多個基準值）；

八、堆排序

? ? ? ? 二叉堆（大頂堆（根節(jié)點的鍵大于左右子樹所有結(jié)點的鍵，并且左右子樹都是大頂堆）；小頂堆（根節(jié)點的鍵小于左右子樹所有結(jié)點的鍵，并且左右子樹都是小頂堆））

????????

把數(shù)組看作一個完全二叉樹；

堆排算法：

把完全二叉樹構(gòu)建成大頂堆，找到第一個非葉子結(jié)點，從后往前構(gòu)建大頂堆

把堆頂元素和無序區(qū)的最后一個元素交換，交換之后無序區(qū)的長度減一，

把無序區(qū)重新調(diào)整成大頂堆，重復(fù)上一步操作，直到無序區(qū)的長度為1；

歸并（缺點：占用內(nèi)存空間復(fù)雜度O（n）），快排，堆排

九、基于比較的排序算法

? ? ? ? 證明：基于比較 的排序算法，時間復(fù)雜度的下限就是O（nlogn）；