對排序算法計(jì)算時間的分析可以遵循若干種不同的準(zhǔn)則，通常以排序過程所需要的算法步數(shù)作為度量，有時也以排序過程中所作的鍵比較次數(shù)作為度量。特別是當(dāng)作一次鍵比較需要較長時間，例如，當(dāng)鍵是較長的字符串時，常以鍵比較次數(shù)作為排序算法計(jì)算時間復(fù)雜性的度量。當(dāng)排序時需要移動記錄，且記錄都很大時，還應(yīng)該考慮記錄的移動次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情況而定。在下面的討論中我們主要考慮用比較的次數(shù)作為復(fù)雜性的度量。
為了對有n個元素的線性表進(jìn)行排序，至少必須掃描線性表一遍以獲取這n個元素的信息，因此排序問題的計(jì)算復(fù)雜性下界為Ω(n)。
如果我們對輸入的數(shù)據(jù)不做任何要求，我們所能獲得的信息就是各個元素的具體的值，我們僅能通過比較來確定輸入序列的元素間次序。即給定兩個元素ai和aj，通過測試aiaj 中的哪一個成立來確定ai和aj間的相對次序。這樣的排序算法稱為比較排序算法。下面我們討論一下比較排序算法在最壞情況下至少需要多少次比較，即比較排序算法的最壞情況復(fù)雜性下界。
我們假設(shè)每次比較只測試ai≤aj ，如果ai≤aj 成立則ai排在aj 前面，否則ai排在aj 后面。任何一個比較排序算法可以描述為一串比較序列:
(ai,aj),(ak,al),..,(am,an),...
表示我們首先比較(ai,aj)，然后比較(ak,al)，...，比較(am,an)，...，直到我們獲取了足夠的信息可以確定所有元素的順序。顯而易見，如果我們對所有的元素兩兩進(jìn)行一次比較的話(總共比較了Cn2次)，就一定可以確定所有元素的順序。但是，如果我們運(yùn)氣足夠好的話，我們可能不必對所有元素兩兩進(jìn)行一次比較。比如說對于有三個元素a1,a2,a3的線性表進(jìn)行排序，如果我們先比較a1和a2，得到a1≤a2；然后比較a2和a3，得到a2≤a3；則不必比較a1和a3，因?yàn)楦鶕?jù)偏序集的傳遞性，必有a1≤a3；但是如果a2≥a3，我們還必須比較a1和a3才能確定a1和a3的相對位置。如果我們適當(dāng)?shù)陌才疟容^的次序的話，也可以減少比較的次數(shù)。這樣我們可以用一棵二叉樹表示比較的順序
該樹的每一個非葉節(jié)點(diǎn)表示一次比較，每一根樹枝表示一種比較結(jié)果，每一個葉節(jié)點(diǎn)表示一種排列順序。這樣的一棵二叉樹叫做決策樹，它用樹枝表示了每次決策做出的選擇。如此我們可以將任何一個比較排序算法用一棵決策樹來表示。
為了對有n個元素的線性表進(jìn)行排序，至少必須掃描線性表一遍以獲取這n個元素的信息，因此排序問題的計(jì)算復(fù)雜性下界為Ω(n)。
如果我們對輸入的數(shù)據(jù)不做任何要求，我們所能獲得的信息就是各個元素的具體的值，我們僅能通過比較來確定輸入序列的元素間次序。即給定兩個元素ai和aj，通過測試aiaj 中的哪一個成立來確定ai和aj間的相對次序。這樣的排序算法稱為比較排序算法。下面我們討論一下比較排序算法在最壞情況下至少需要多少次比較，即比較排序算法的最壞情況復(fù)雜性下界。
我們假設(shè)每次比較只測試ai≤aj ，如果ai≤aj 成立則ai排在aj 前面，否則ai排在aj 后面。任何一個比較排序算法可以描述為一串比較序列:
(ai,aj),(ak,al),..,(am,an),...
表示我們首先比較(ai,aj)，然后比較(ak,al)，...，比較(am,an)，...，直到我們獲取了足夠的信息可以確定所有元素的順序。顯而易見，如果我們對所有的元素兩兩進(jìn)行一次比較的話(總共比較了Cn2次)，就一定可以確定所有元素的順序。但是，如果我們運(yùn)氣足夠好的話，我們可能不必對所有元素兩兩進(jìn)行一次比較。比如說對于有三個元素a1,a2,a3的線性表進(jìn)行排序，如果我們先比較a1和a2，得到a1≤a2；然后比較a2和a3，得到a2≤a3；則不必比較a1和a3，因?yàn)楦鶕?jù)偏序集的傳遞性，必有a1≤a3；但是如果a2≥a3，我們還必須比較a1和a3才能確定a1和a3的相對位置。如果我們適當(dāng)?shù)陌才疟容^的次序的話，也可以減少比較的次數(shù)。這樣我們可以用一棵二叉樹表示比較的順序
該樹的每一個非葉節(jié)點(diǎn)表示一次比較，每一根樹枝表示一種比較結(jié)果，每一個葉節(jié)點(diǎn)表示一種排列順序。這樣的一棵二叉樹叫做決策樹，它用樹枝表示了每次決策做出的選擇。如此我們可以將任何一個比較排序算法用一棵決策樹來表示。