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