C++排序算法

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

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

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

11.1.1   評(píng)價(jià)維度

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

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

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

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

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

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

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

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

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

11.1.2   理想排序算法

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

接下來(lái)，我們將共同學(xué)習(xí)各種排序算法，并基于上述評(píng)價(jià)維度對(duì)各個(gè)排序算法的優(yōu)缺點(diǎn)進(jìn)行分析。