摘 要：排序是數(shù)據(jù)處理領(lǐng)域中最常用的一種運(yùn)算。排序的目的之一是方便查找。對(duì)于一個(gè)順序存儲(chǔ)的線性表，若不經(jīng)過排序而查找，則時(shí)間復(fù)雜度為O（n），若在排序的基礎(chǔ)上進(jìn)行二分查找，則時(shí)間復(fù)雜度可提高到O（logn），效果是相當(dāng)顯著的。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu) 排序 方法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2012）12（b）-0027-02

1 排序的基本概念

排序就是把一組記錄按照某個(gè)領(lǐng)域的值的遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。通常把用于排序的域稱為排序域或排序項(xiàng)，把該域中的每一個(gè)值（它與一個(gè)記錄相對(duì)應(yīng)）稱為排序碼。

記錄的排序碼可以是記錄的關(guān)鍵字，也可以是任何非關(guān)鍵字，所以排序碼相同的記錄可能只有一個(gè)，也可能有多個(gè)。對(duì)于具有同一個(gè)排序碼的多個(gè)記錄來說，若采用的排序方法使排序后記錄的相對(duì)次序不變，則稱此排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。

2 排序的方法

排序的方法很多，一般分為插入排序法、交換排序法、選擇排序法、歸并排序法四種。

2.1 插入排序法

插入排序法包括直接插入排序和希爾排序。

（1）直接插入排序：直接插入排序是一種最簡(jiǎn)單的排序方法。

1）算法思想：直接插入排序的基本思想是：逐個(gè)處理待排序列中的記錄，將其與前面已經(jīng)排好序的子序中的記錄進(jìn)行比較，確定要插入的位置，并將記錄插入到子序中。具體做法如以下幾點(diǎn)。

①開始時(shí)，把第①個(gè)記錄看成是已經(jīng)排好序的子序，這時(shí)子序中只有一個(gè)記錄。

②從第②個(gè)記錄起到最后一個(gè)記錄，依次將記錄和前面子序中的記錄比較，確定記錄插入的位置。

③將記錄插入到子序中，子序記錄個(gè)數(shù)加1，直至子序長(zhǎng)度和原來待排序列長(zhǎng)度一致時(shí)結(jié)束。

2）算法分析。

①直接插入排序的時(shí)間復(fù)雜度為O（n2）。

②直接插入排序是穩(wěn)定的。適用于記錄個(gè)數(shù)較少的場(chǎng)合。

（2）希爾排序：希爾排序又稱縮小增量排序，是對(duì)直接插入排序的一種改進(jìn)。

1）算法思想：希爾排序的基本思想是：先將n個(gè)待排序記錄序列分割成若干個(gè)子序列，然后對(duì)各子序列分別進(jìn)行排序，當(dāng)整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。具體做法如以下幾點(diǎn)。

①取定一個(gè)正整數(shù)d1

②取定一個(gè)正整數(shù)d2

希爾提出的di取法為d1=n/2，di+1=di/2。

2）算法分析。

①希爾排序的速度一般要比直接插入排序快。

②希爾排序是不穩(wěn)定的。

2.2 交換排序法

交換排序法包括冒泡排序和快速排序兩種。

（1）冒泡排序：冒泡排序是一種簡(jiǎn)單交換排序

1）算法思想：冒泡排序的基本思想是。

①將第n個(gè)記錄的關(guān)鍵字和第n-1個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄進(jìn)行交換，若為正序則保持原序。

②將第n-1個(gè)記錄的關(guān)鍵字和第n-2個(gè)記錄的關(guān)鍵字進(jìn)行比較，重復(fù)上述排序過程。

③將上述①和②的排序過程稱做第一趟冒泡排序，其結(jié)果使得關(guān)鍵字最小的記錄被安置到第1個(gè)記錄的位置上。

④進(jìn)行第2趟冒泡排序，從第n個(gè)記錄開始至第2個(gè)記錄進(jìn)行同樣的操作，其結(jié)果是使得關(guān)鍵字次大的記錄被安置到第2個(gè)記錄的位置上。

依此類推，第i趟冒泡排序是從第n個(gè)記錄到第i個(gè)記錄之間依次比較和交換。設(shè)有n個(gè)關(guān)鍵字，需要經(jīng)過n-1趟比較和交換，就使得n個(gè)記錄的關(guān)鍵字從小到大，自上而下的排好序了，整個(gè)過程就像氣泡一個(gè)個(gè)地往上冒一樣，故稱為冒泡排序。

（2）算法分析。

①冒泡排序的時(shí)間復(fù)雜度為O（n2）。

②冒泡排序是穩(wěn)定的。適用于記錄基本有序的場(chǎng)合。

（2）快速排序：快速又稱分區(qū)交換法，是對(duì)冒泡排序的一種改進(jìn)?？焖倥判蚴悄壳皟?nèi)部排序中速度較快的一種方法。

1）算法思想：快速排序的基本思想是：通過一趟排序?qū)⒋判虻膎個(gè)記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可以分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。具體操作如以下幾點(diǎn)。

①設(shè)待排序的記錄序列存于{L.r[s]，L.r[s+1]，…，L.r[t]}中，首先選取一個(gè)記錄（通常選取第一個(gè)記錄L.r[s]）作為“樞軸”。

②按以下原則重新排列其余記錄：將所有關(guān)鍵字比“樞軸”記錄小的都安置在其位置之前，將所有關(guān)鍵字比“樞軸”記錄大的都安置在其位置之后。由此，可以該“樞軸”記錄最后所落的位置i作為分界線，將帶排序記錄{L.r[s]，L.r[s+1]，…，L.r[t]}分割成兩個(gè)子序列{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[s+1]，…，L.r[t]}。這個(gè)過程稱做一趟快速排序。

③對(duì)所分割的兩部分分別重復(fù)上述過程，直至每個(gè)部分內(nèi)只剩下一個(gè)記錄排序。快速排序完成。

2）算法分析。

①希爾排序的平均時(shí)間復(fù)雜度為O（nlo g2n）。

②快速排序是不穩(wěn)定的。

2.3 選擇排序法

選擇排序法包括直接選擇排序和堆排序兩種。

（1）直接選擇排序：直接選擇排序是一種最簡(jiǎn)單且最為大家熟悉的一種選擇排序法。

1）算法思想：直接選擇排序的基本思想是：設(shè)n個(gè)待排序的記錄存放在L.r[1..n]中，對(duì)n個(gè)待排序記錄進(jìn)行n-1趟掃描。

①第一趟掃描選出n個(gè)記錄中關(guān)鍵字最小的記錄，并與L.r[1]記錄交換位置。

②第二趟掃描選出余下的n-1個(gè)記錄中關(guān)鍵字值最的記錄，并與L.r[2]記錄交換位置。

依此類推，直至第n-1趟掃描結(jié)束，所有記錄有序?yàn)橹埂?/p>

2）算法分析。

①直接選擇排序時(shí)間復(fù)雜度為O（n2）。

②直接選擇排序是不穩(wěn)定的。

（2）堆排序。

1）堆排序的方法：關(guān)鍵步驟有兩個(gè)：第①是構(gòu)造堆，即如何將一個(gè)無(wú)序序列建成初始堆壘；第②是調(diào)整堆，即如何在輸出堆壘的根結(jié)點(diǎn)之后，調(diào)整剩余元素成為一個(gè)新的堆壘。首先考慮第二個(gè)問題，調(diào)整堆；然后再考慮第一個(gè)問題，構(gòu)造堆。

①調(diào)整堆。假設(shè)輸出堆根結(jié)點(diǎn)之后，以堆的最后一個(gè)元素替代之。此時(shí)根結(jié)點(diǎn)的左子樹和右子樹均為堆壘，則只需要自上而下進(jìn)行調(diào)整即可。首先將根結(jié)點(diǎn)與它的左、右子結(jié)點(diǎn)比較，如果根結(jié)點(diǎn)比它的兩個(gè)子結(jié)點(diǎn)都小，則已經(jīng)是堆壘；否則，讓根結(jié)點(diǎn)與其中較小的子結(jié)點(diǎn)交換，先讓根結(jié)點(diǎn)滿足堆的性質(zhì)?？赡芤?yàn)榻粨Q，使以交換后的結(jié)點(diǎn)為根的子樹不再滿足堆的性質(zhì)，則重復(fù)向下調(diào)整。當(dāng)調(diào)整使新的更小子樹依舊滿足堆的性質(zhì)時(shí)，重新建堆壘過程結(jié)束；當(dāng)交換使新的更小的子樹不再滿足堆的性質(zhì)時(shí)，繼續(xù)按上述方法調(diào)整被破壞的更小子樹。最壞的情況是直至調(diào)整到葉結(jié)點(diǎn)才結(jié)束。這種自上而下調(diào)整建堆的過程稱為結(jié)點(diǎn)向下“篩選”。

②構(gòu)造堆。為構(gòu)造初始堆，可以在已是堆的兩個(gè)子序列上面加上它們的根結(jié)點(diǎn)，并且做必要的調(diào)整使之成為更大的堆壘。加上根結(jié)點(diǎn)后，可能不滿足堆的定義，則可以用前述的“篩選”方法，使之成為堆。所以，從一個(gè)無(wú)序序列構(gòu)造堆的過程就是反復(fù)“篩選”的過程。若將n個(gè)待排序記錄的關(guān)鍵字序列看成是一個(gè)完全二叉樹，則最后一個(gè)非葉子結(jié)點(diǎn)是第n/2個(gè)元素。首先，將n個(gè)葉子結(jié)點(diǎn)看成n個(gè)堆，然后從第n/2個(gè)結(jié)點(diǎn)開始，依次將第n/2個(gè)結(jié)點(diǎn)，第n/2-1個(gè)結(jié)點(diǎn)，……，第1個(gè)結(jié)點(diǎn)按照堆的定義逐一加到它們的子結(jié)點(diǎn)上，直到建成一個(gè)完全的堆壘。

2）算法分析。

①堆排序在最壞的情況下，其時(shí)間復(fù)雜度也為O（nlog2n）。

②堆排序是不穩(wěn)定的。不適用于記錄較少的情況。

2.4 歸并排序法

歸并排序的基本思想是：將兩個(gè)或兩個(gè)以上的有序序列歸并成一個(gè)有序序列。

（1）兩個(gè)有序序列的歸并：將兩個(gè)有序序列歸并為一個(gè)新有有序序列，稱為2-路歸并，其核心是將一維數(shù)組中前后相鄰的兩個(gè)有序序列合并為一個(gè)有序序列。

（2）一趟歸并排序。

1）算法思想：對(duì)于有n個(gè)記錄的無(wú)序序列進(jìn)行歸并排序，其基本思想是。

①將n個(gè)待排序的記錄分成只含有1個(gè)記錄的n個(gè)有序子序列。

②將這n個(gè)有序子序列依次兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列（當(dāng)n為奇數(shù)時(shí)，有一個(gè)長(zhǎng)度為1的子序列）。

③再對(duì)它們作兩兩合并，……，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序表為止，歸并排序完成。

2）算法分析。

①歸并排序時(shí)間復(fù)雜度為O（nlogn）。

②歸并排序是穩(wěn)定的。

參考文獻(xiàn)

[1]江濤.中央廣播電視大學(xué)出版社[M]，1999（10）.

[2]許卓群.中央廣播電視大學(xué)出版社[M]，2001（2）.

[3]彭波.清華大學(xué)出版社[M]，2003（6）.