C++排序算法

「排序算法 sorting algorithm」用于對一組數(shù)據(jù)按照特定順序進行排列。排序算法有著廣泛的應用，因為有序數(shù)據(jù)通常能夠被更有效地查找、分析和處理。

如圖 11-1 所示，排序算法中的數(shù)據(jù)類型可以是整數(shù)、浮點數(shù)、字符或字符串等。排序的判斷規(guī)則可根據(jù)需求設定，如數(shù)字大小、字符 ASCII 碼順序或自定義規(guī)則。

圖 11-1   數(shù)據(jù)類型和判斷規(guī)則示例

11.1.1   評價維度

運行效率：我們期望排序算法的時間復雜度盡量低，且總體操作數(shù)量較少（即時間復雜度中的常數(shù)項降低）。對于大數(shù)據(jù)量情況，運行效率顯得尤為重要。

就地性：顧名思義，「原地排序」通過在原數(shù)組上直接操作實現(xiàn)排序，無須借助額外的輔助數(shù)組，從而節(jié)省內存。通常情況下，原地排序的數(shù)據(jù)搬運操作較少，運行速度也更快。

穩(wěn)定性：「穩(wěn)定排序」在完成排序后，相等元素在數(shù)組中的相對順序不發(fā)生改變。

穩(wěn)定排序是多級排序場景的必要條件。假設我們有一個存儲學生信息的表格，第 1 列和第 2 列分別是姓名和年齡。在這種情況下，「非穩(wěn)定排序」可能導致輸入數(shù)據(jù)的有序性喪失。

# 輸入數(shù)據(jù)是按照姓名排序好的
# (name, age)
  ('A', 19)
  ('B', 18)
  ('C', 21)
  ('D', 19)
  ('E', 23)

# 假設使用非穩(wěn)定排序算法按年齡排序列表，
# 結果中 ('D', 19) 和 ('A', 19) 的相對位置改變，
# 輸入數(shù)據(jù)按姓名排序的性質丟失
  ('B', 18)
  ('D', 19)
  ('A', 19)
  ('C', 21)
  ('E', 23)

自適應性：「自適應排序」的時間復雜度會受輸入數(shù)據(jù)的影響，即最佳、最差、平均時間復雜度并不完全相等。

自適應性需要根據(jù)具體情況來評估。如果最差時間復雜度差于平均時間復雜度，說明排序算法在某些數(shù)據(jù)下性能可能劣化，因此被視為負面屬性；而如果最佳時間復雜度優(yōu)于平均時間復雜度，則被視為正面屬性。

是否基于比較：「基于比較的排序」依賴于比較運算符（<、=、>）來判斷元素的相對順序，從而排序整個數(shù)組，理論最優(yōu)時間復雜度為 O(nlog?n) 。而「非比較排序」不使用比較運算符，時間復雜度可達 O(n) ，但其通用性相對較差。

11.1.2   理想排序算法

運行快、原地、穩(wěn)定、正向自適應、通用性好。顯然，迄今為止尚未發(fā)現(xiàn)兼具以上所有特性的排序算法。因此，在選擇排序算法時，需要根據(jù)具體的數(shù)據(jù)特點和問題需求來決定。

接下來，我們將共同學習各種排序算法，并基于上述評價維度對各個排序算法的優(yōu)缺點進行分析。