數據結構中排序方法的研究

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

關鍵詞：數據結構 排序 方法

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

1 排序的基本概念

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

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

2 排序的方法

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

2.1 插入排序法

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

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

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

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

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

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

2）算法分析。

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

②直接插入排序是穩定的。適用于記錄個數較少的場合。

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

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

①取定一個正整數d1

②取定一個正整數d2

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

2）算法分析。

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

②希爾排序是不穩定的。

2.2 交換排序法

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

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

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

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

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

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

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

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

（2）算法分析。

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

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

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

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

①設待排序的記錄序列存于{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]}。這個過程稱做一趟快速排序。

③對所分割的兩部分分別重復上述過程，直至每個部分內只剩下一個記錄排序。快速排序完成。

2）算法分析。

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

②快速排序是不穩定的。

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）。

②直接選擇排序是不穩定的。

（2）堆排序。

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

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

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

2）算法分析。

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

②堆排序是不穩定的。不適用于記錄較少的情況。

2.4 歸并排序法

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

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

（2）一趟歸并排序。

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

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

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

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

2）算法分析。

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

②歸并排序是穩定的。

參考文獻

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

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

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