第九章 排序

9.1 特殊條件排序

第七章中我們用 中的 sort 函數來排序。但是它只能依數值由小到大排序。可是如果遇到特殊條件的排序，Sort 就不知道要如何去排了。

這題的排序條件很詭異。

9.2 字典序

給你一串陣列，，要你找出下一個排列

規則

1. 找出最右邊一組a[x]小於a[x+1]
2. 找不到時已經到最大排列，停止搜尋
3. 否則找出在a[x]右邊大裕a[x]，的最小值a[y]
4. 交換a[x]和a[y]
5. 翻轉a[x]的序列
6. 所得排列即得所求

以下是範例程式碼

next_permutation

c++裡已有內建字典序排列，是在的next_permutation

範例如下

是不是簡潔許多?

9.3 排序演算法

在第七章使用"algorithm"裡的sort解題目時，你可能遇到TLE，這時你可能會懷疑是不是自己寫出無限迴圈，但其實是sort讓你超過時間了，在wiki的排序演算法內有各種演算法，例如sort是內省排序。這些演算法各有優缺點，有的省時，有的省空間，有的很好寫，以下介紹幾種

氣泡排序是一種最基本的排序，是兩兩元素做比較然後交換。時間複雜度為O(n^2)，空間複雜度為O(n)。

範例程式碼

合併排序法是使用分治法的概念，先將陣列分成兩半，再將兩個小陣列進行比大小，合併成一個陣列，以此類推，時間複雜度為O(n log n)，空間複雜度為O(n)

範例程式碼

計數排序是一種線性時間排序算法，須先開一個陣列來計算各個數字的總數，再開另一個陣列，把數字由小(大)到大(小)填入，時間複雜度為O(n+k)，空間複雜度為O(n+k)，n為陣列大小，k為數字範圍。

範例程式碼

補充資料