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

關鍵詞：數(shù)據(jù)結構 排序 方法

中圖分類號：TP311 文獻標識碼：A 文章編號：1672-3791（2012）12（b）-0027-02

1 排序的基本概念

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

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

2 排序的方法

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

2.1 插入排序法

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

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

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

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

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

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

2）算法分析。

①直接插入排序的時間復雜度為O（n2）。

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

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

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

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

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

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

2）算法分析。

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

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

2.2 交換排序法

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

（1）冒泡排序：冒泡排序是一種簡單交換排序

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

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

②將第n-1個記錄的關鍵字和第n-2個記錄的關鍵字進行比較，重復上述排序過程。

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

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

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

（2）算法分析。

①冒泡排序的時間復雜度為O（n2）。

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

（2）快速排序：快速又稱分區(qū)交換法，是對冒泡排序的一種改進。快速排序是目前內(nèi)部排序中速度較快的一種方法。

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

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

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

③對所分割的兩部分分別重復上述過程，直至每個部分內(nèi)只剩下一個記錄排序?？焖倥判蛲瓿?。

2）算法分析。

①希爾排序的平均時間復雜度為O（nlo g2n）。

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

2.3 選擇排序法

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

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

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

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

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

依此類推，直至第n-1趟掃描結束，所有記錄有序為止。

2）算法分析。

①直接選擇排序時間復雜度為O（n2）。

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

（2）堆排序。

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

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

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

2）算法分析。

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

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

2.4 歸并排序法

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

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

（2）一趟歸并排序。

1）算法思想：對于有n個記錄的無序序列進行歸并排序，其基本思想是。

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

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

③再對它們作兩兩合并，……，如此重復，直到得到一個長度為n的有序表為止，歸并排序完成。

2）算法分析。

①歸并排序時間復雜度為O（nlogn）。

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

參考文獻

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

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

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