本章按

①插入類(lèi)排序（插入、希爾）②選擇類(lèi)排序（選排、堆排）③交換類(lèi)排序（冒泡、快排）④歸并類(lèi)排序（歸并）展開(kāi)介紹。需要特別注意其中快排的劃分算法、歸并排序合并兩個(gè)有序序列的算法、堆排序引入的二叉堆等。了解掌握不同排序算法的時(shí)間空間復(fù)雜度與是否穩(wěn)定。

插入類(lèi)排序（插排、希爾）

其核心思想是將待排序元素劃分為“已排序”和“未排序”兩部分，每次從“未排序”的元素中選擇一個(gè)插入到“已排序”的元素中。

①插入排序

平均時(shí)間復(fù)雜度：O(N^2)，空間復(fù)雜度O(1)。

②希爾排序（或稱縮小增量排序）

每趟排序都會(huì)將原序列分割成間隔為h的不同子序列，并通過(guò)插入排序?qū)λ凶有蛄羞M(jìn)行排序，每趟排序所取的間隔h逐漸縮小至1，此時(shí)相當(dāng)于對(duì)原序列進(jìn)行一次插入排序。若序列長(zhǎng)度為n，通常選取的比較好的增量序列為。

時(shí)間復(fù)雜度：?O(N^7/6)~O(N^3/2)，空間復(fù)雜度O(1)。

選擇類(lèi)排序：選擇排序、堆排序

其核心思想是每次找出整個(gè)序列中第i小的關(guān)鍵字，并將它與位于第i個(gè)位置的關(guān)鍵字交換，這樣操作n次后，整個(gè)序列就有序了。

①選擇排序

平均時(shí)間復(fù)雜度：?O(N^2)，空間復(fù)雜度O(1)。

②堆排序

堆排序相較于選擇排序，它引入了二叉堆這一數(shù)據(jù)結(jié)構(gòu)，將尋找最小值的操作的時(shí)間復(fù)雜度從O(N)降低到O(logN)。由于二叉堆是一棵完全二叉樹(shù)，因此可以用一個(gè)數(shù)組存儲(chǔ)這個(gè)二叉堆。

平均時(shí)間復(fù)雜度：?O(NlogN)，空間復(fù)雜度O(1)。

C++的priority_queue就是大根堆的一種實(shí)現(xiàn)。有關(guān)題目中，只需掌握與堆相關(guān)的泛型算法即可（make_heap、is_heap、heap_sort）。

交換類(lèi)排序：冒泡排序、快速排序

交換類(lèi)排序是通過(guò)交換逆序關(guān)鍵字進(jìn)行排序的方法。（對(duì)待排序列s，若i<j且s[i]>s[j]，則稱s[i]和s[j]為一對(duì)逆序關(guān)鍵字）

①冒泡排序

每次檢查相鄰兩個(gè)元素，若前面的關(guān)鍵字大于后面的關(guān)鍵字（此處排成升序），就將相鄰的兩個(gè)關(guān)鍵字交換。

平均時(shí)間復(fù)雜度：?O(N^2)，空間復(fù)雜度O(1)。

②快速排序

按基值（樞紐元）劃分左右區(qū)間并歸位基值?？炫旁谛蛄杏行驎r(shí)性能最差，但可以稍加調(diào)整避免這種情況，并可以和堆排序結(jié)合（因?yàn)槎雅判蜃顗亩加蠴(NlogN)），即可保證對(duì)幾乎所有輸入都可達(dá)到不超過(guò)O(NlogN)的時(shí)間復(fù)雜度。

平均時(shí)間復(fù)雜度：?O(NlogN)，空間復(fù)雜度O(N)。

注意其中相關(guān)的partition劃分算法：void?partition(b,e,p1)/void stable_partition(b,e,p1)和bool?is_partitioned(b,e,p1)的使用。

歸并類(lèi)排序：歸并排序

應(yīng)用分治思想的遞歸算法，對(duì)序列s進(jìn)行歸并排序的具體步驟為①：若s關(guān)鍵字的個(gè)數(shù)為0或1，不需排序，直接返回；②將s分為左半部分序列s1與右半部分序列s2，對(duì)s1和s2分別進(jìn)行歸并排序；③將排序后的有序序列s1和s2合并為一個(gè)有序序列s。

其中第3步中需開(kāi)辟一個(gè)數(shù)組存儲(chǔ)最終合并后的s，空間復(fù)雜度為O(N)。其原理是利用雙指針?lè)謩e從兩個(gè)有序序列中選擇最小的值放入數(shù)組，直到遍歷完兩個(gè)序列。

其中合并兩個(gè)有序序列為線性算法，此外需要遞歸調(diào)用，因此時(shí)間復(fù)雜度為O(NlogN)。但由于合并的過(guò)程中需要開(kāi)辟數(shù)組存儲(chǔ)合并結(jié)果，因此空間復(fù)雜度為O(N)。

注意C++標(biāo)準(zhǔn)庫(kù)中合并的泛型算法_OIter merge(b,e,b2,e2,d)/_OIter merge(b,e,b2,e2,d,p2)與void inplace_merge(b,m,e)/void inplace_merge(b,m,e,p2)的用法。

可以自己模擬一下兩個(gè)有序序列的合并過(guò)程：

回顧sort相關(guān)泛型算法

bool is_sorted(b,e)/bool is_sorted(b,e,p2)：表示序列是否按序列排列；

_FIter is_sorted_until(b,e)/_FIter?is_sorted_until(b,e,p2)：查找從第一個(gè)元素開(kāi)始最長(zhǎng)升序連續(xù)子序列，返回尾后迭代器；

void?partial_sort(b,m,e)/void?partial_sort(b,m,e,p2)：將b到e序列中從小到大將元素放到b到m區(qū)間中，其余放到m到e區(qū)間中（用于找到序列中最小的m-b個(gè)數(shù)/前m-b個(gè)最小值）；

void nth_element(b,m,e)/void?nth_element(b,m,e,p2)：使迭代器m指向的元素恰好是整個(gè)序列排好序后該位置上的值（用于找到序列中第m-b+1個(gè)最小值）。