⑴ 線性時間復雜度(O(n))的排序演算法小結
目前我掌握的線性時間復雜度(O(n))的排序演算法有三個: 計數排序, 基數排序, 桶排序.
計數排序, 適用於小范圍的整數型元素的數組排序, 其原理是對各個元素值統計頻次, 然後從小到大掃描, 將各個元素值重復若干次. 比如對序列進行排序, 可以得到最終的排序結果: 0, 1,1,1,2,2,3,3,3,3,3,4. 計數排序的優點是非常簡單, O(n)中的常數項會非常小, 但缺點是如果元素值范圍非常大, 那麼幾乎不會出現重復的元素, 造成效率低下, 且也開不了這么大(10^16)的數組用於計數, 如果元素值是浮點數的話, 也幾乎不會出現兩個相等的元素.
基數排序的原理非常類似於人類對數字大小的理解, 即依次觀察每一位. 以數組為例, 先按照個位數, 分別將那些數字安放在10個桶裡面, 然後從左到右, 將那些數字拿出來, 接下里, 基於十位數(如果數字小於10, 那麼補零), 做類似的事情, 因為最大數字最多隻有2位數字, 因此, 排序結束了. 思考一下這個過程的原理, 最高位對數字大小的影響最大, 因此, 必須放在最後一步, 位越高, 對數字大小的影響越大, 因此, 演算法的順序必須是從低位到高位.
分桶排序類似於直方圖, 直方圖裡面的一個方塊是一個"桶". 比如數值范圍在0到10, 如果均勻分成10個桶的話, 每個桶的區間為[0, 1), [1, 2), [2, 3),....,[9, 10), 如果元素為0.5, 那麼將0.5放在區間[0, 1). 很明顯, 落在右邊桶的元素要比落在左邊桶的元素更大. 而落在同一個桶裡面的元素, 相互之間無法比較大小. 如果桶的個數足夠多, 那麼每個桶裡面的元素個數就比較少了, 桶內元素使用基於比較的排序演算法進行排序(時間復雜度為N*log(N)). 最後從左到右, 從桶里取出元素, 完成了排序.
總結: 計數排序適用於小范圍的整數型元素的數組排序, 基數排序適用於整數型元素, 不怕數值范圍太大, 這點要比計數排序強, 分桶排序可以用在浮點型元素(當然, 也可以用於整數型元素).
⑵ O（n2）排序演算法的總結
最近在慕課網上學習了O（n2）時間復雜度的相關演算法，總算是對這些演算法的優缺點有了詳細的特點。其實對於任何的演算法，沒有優點和缺點，而是有相應的特點。所以我們應該結合不同的排序環境來選擇不同的排序演算法，從而達到在實現時間和執行效率上的平衡。這是因為，越是簡單的排序演算法，實現起來肯定是越容易，而且出現BUG的概率也不會太大。相反，復雜演算法可能效率更高，但是出現問題的可能性也會更大。下面，我就結合O（n2）時間復雜度的四個經典排序演算法，為您詳細講解這四個演算法的特點。
定義：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
圖示說明：
源碼實現：
分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進行兩次循環，而且最關鍵的是內層循環在每一次執行時都是全部執行完的。那我們有沒有辦法讓內層循環不用每次都執行完呢？方法肯定是有的，這就是冒泡排序。
定義：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，從執行次數上來說，冒泡排序是比選擇排序的循環次數更少的。那是不是就可以說，如果待排序的數組中元素比較合適，冒泡排序在時間復雜度上是不是會比選擇排序更好呢？真的是這樣的嗎？
其實不是的，經過多次測試驗證，冒泡排序基本上是比選擇排序的時間復雜度要差的，這是為什麼呢？從源碼中我們可以很明顯的看出來，雖然冒泡排序是比選擇排序執行次數少了，但是交換的次數明顯增多了，而如果你對計算機程序指令的實現原理只要有一個基本的認識，就應該知道交換動作比賦值動作是需要更多指令操作的。所以說，最終冒泡排序大部分情況下，比選擇排序的時間復雜度都要高。
既然交換動作這么消耗資源，那有沒有一種方法，即能夠減少內層循環的執行次數，又可以減少甚至是無需交換操作呢？這就要請出插入排序了。
定義：插入排序（Insertion Sort）的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，即每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，插入排序（優化後的）是沒有交換操作的，而且對於內層循環來說，如果待排序的元素是比較大的值，那內層循環執行的次數會非常的少。因此，如果原始數據基本上是有序的，那使用插入排序的效率會非常的高。在O（n2）級別的排序演算法還可以再優化嗎？如果可以從哪裡優化呢？下面我們來介紹希爾排序，正是這個排序演算法的提出，使得排序演算法打破了O（n2）時間復雜度的禁錮。
定義：希爾排序(Shell's Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。該演算法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，排序演算法便終止。
對於希爾排序來說，最關鍵的就是增量該如何選取。這個增量該怎麼確定，這還真是個數學難題，至今沒有解答。但是通過大量的實驗，還是有個經驗值的。我們的例子給出的增量選取公式是：h = 3 * h + 1，下面請看圖示說明。
圖示說明：
源碼實現：
分析：從插入排序中我們知道，插入排在待排序數組基本有序時，插入排序的演算法效率會非常高，所以我們可以這樣認為，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，在對全體進行一次直接插入排序。
而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當h值大的時候，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長。這是非常有效率的。而當h減小時，每一趟排序需要移動的元素的個數增多，但是此時數據項已經接近於它們排序後最終的位置，這對於插入排序可以更有效率。正是這兩種情況的結合才使希爾排序效率那麼高。
對於增量的選取，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2，簡單地把每一趟排序分成了兩半。但是，這被證明並不是最好的數列。盡管對於大多數的數據來說這個方法還是比插入排序效果好，但是這種方法有時會使運行時間降到O(N2)，這並不比插入排序的效率更高。間隔序列中的數字互質通常被認為很重要：也就是說，除了1之外它們沒有公約數。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果。希爾最初以N/2為間隔的低效性就是歸咎於它沒有遵守這個准則。
總結：上面就是四種經典O（n2）級別排序演算法的相關說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的，因為使用場景基本沒有。而對於插入排序和希爾排序來說，在待排序數據基本有序的情況下，使用場景還是有的，比如一些日誌文件中存儲的日誌，可能大部分的日誌記錄都是基於時間排序，只是在某些極端情況下導致一些日誌晚存儲了導致時間不一致。
我是徐建航， 這是我寫的第31篇文章，歡迎你加入007社群，七天寫一篇，一起寫七年，七年之後一起去南極。
⑶ 幾種經典排序演算法優劣比較的C++程序實現
一、低級排序演算法
1.選擇排序
（1）排序過程
給定一個數值集合，循環遍歷集合，每次遍歷從集合中選擇出最小或最大的放入集合的開頭或結尾的位置，下次循環從剩餘的元素集合中遍歷找出最小的並如上操作，最後直至所有原集合元素都遍歷完畢，排序結束。
（2）實現代碼
//選擇排序法
template
void Sort：：SelectSort（T* array， int size）
{
int minIndex；
for（int i = 0； i < size； i++）
{
minIndex = i；
for（int j = i + 1； j < size； j++）
{
if（array[minIndex] > array[j]）
{
minIndex = j；
}
}
if（minIndex ！= i）
{
Swap（array， i， minIndex）；
}
}
}
（3）分析總結
選擇排序時間復雜度比較高，達到了O（n^2），每次選擇都要遍歷一遍無序區間。選擇排序對一類重要的元素序列具有較好的效率，就是元素規模很大，而排序碼卻比較小的序列。另外要說明的是選擇排序是一種不穩定的排序方法。
2.冒泡排序
（1）排序過程
冒泡排序的過程形如其名，就是依次比較相鄰兩個元素，優先順序高（或大或小）的元素向後移動，直至到達序列末尾，無序區間就會相應地縮小。下一次再從無序區間進行冒泡操作，依此循環直至無序區間為1，排序結束。
（2）實現代碼
//冒泡排序法
template
void Sort：：BubbleSort（T* array， int size）
{
for（int i = 0； i < size； i++）
{
for（int j = 1； j < size - i； j++）
{
if（array[j] < array[j - 1]）
{
Swap（array， j， j - 1）；
}
}
}
}
（3）分析總結
冒泡排序的時間復雜度也比較高，達到O（n^2），每次遍歷無序區間都將優先順序高的元素移動到無序區間的末尾。冒泡排序是一種穩定的排序方式。
二、高級排序演算法
（1）排序過程
歸並排序的原理比較簡單，也是基於分治思想的。它將待排序的元素序列分成兩個長度相等的子序列，然後為每一個子序列排序，然後再將它們合並成一個序列。
（2）實現代碼
//歸並排序
template
void Sort：：MergeSort（T* array， int left， int right）
{
if（left < right）
{
int mid = （left + right） / 2；
MergeSort（array， left， mid）；
MergeSort（array， mid + 1， right）；
Merge（array， left， mid， right）；
}
}
//合並兩個已排好序的子鏈
template
void Sort：：Merge（T* array， int left， int mid， int right）
{
T* temp = new T[right - left + 1]；
int i = left， j = mid + 1， m = 0；
while（i <= mid && j <= right）
{
if（array[i] < array[j]）
{
temp[m++] = array[i++]；
}
else
{
temp[m++] = array[j++]；
}
}
while（i <= mid）
{
temp[m++] = array[i++]；
}
while（j <= right）
{
temp[m++] = array[j++]；
}
for（int n = left， m = 0； n <= right； n++， m++）
{
array[n] = temp[m]；
}
delete temp；
}
（3）分析總結
歸並排序最好、最差和平均時間復雜度都是O（nlogn），是一種穩定的排序演算法。