排序定義將一個數(shù)據(jù)元素(或記錄的任意序列

1、Sorting排 序 排序定義排序定義將一個數(shù)據(jù)元素（或記錄）的任意序列，將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列叫重新排列成一個按關(guān)鍵字有序的序列叫 排序分類排序分類u按待排序記錄所在位置按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問的排序外部排序：排序過程中需對外存進行訪問的排序u按排序依據(jù)原則按排序依據(jù)原則 插入排序：直接插入排序、折半插入排序、希爾排序插入排序：直接插入排序、折半插入排序、希爾排序 交換排序：冒泡排序、快速排序交換排序：冒泡排序、快速排序 選擇排序：簡單選擇排序、堆排序選擇

2、排序：簡單選擇排序、堆排序 歸并排序：歸并排序：2-路歸并排序路歸并排序 基數(shù)排序基數(shù)排序u按排序所需工作量按排序所需工作量簡單的排序方法：簡單的排序方法：T(n)=O(n)先進的排序方法：先進的排序方法：T(n)=O(nlogn) 基數(shù)排序：基數(shù)排序：T(n)=O(d.n)排序基本操作排序基本操作u比較兩個關(guān)鍵字大小比較兩個關(guān)鍵字大小u將記錄從一個位置移動到另一個位將記錄從一個位置移動到另一個位置置排序方法排序方法插入排序插入排序選擇排序選擇排序交換排序交換排序歸并排序歸并排序直接插入排序直接插入排序折半插入排序折半插入排序簡單選擇排序簡單選擇排序堆排序堆排序起泡排序起泡排序快速排序快速排序

3、 基數(shù)排序基數(shù)排序多關(guān)鍵字排序多關(guān)鍵字排序u定義：定義：例例 對對52張撲克牌按以下次序排序：張撲克牌按以下次序排序： 2 3 A 2 3 A 2 3 A 2 3 A兩個關(guān)鍵字：花色（兩個關(guān)鍵字：花色（ ） 面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”u多關(guān)鍵字排序方法多關(guān)鍵字排序方法最高位優(yōu)先法（最高位優(yōu)先法（MSD)：先對最高位：先對最高位關(guān)鍵字關(guān)鍵字k1（如花色）排序，將序列（如花色）排序，將序列分成若干子序列，每個子序列有相同分成若干子序列，每個子序列有相同的的k1值；然后讓每個子序列對次關(guān)值；然后讓每個子序列對次關(guān)鍵字鍵字k2（如面值）排序，又分成若（如面值）

4、排序，又分成若干更小的子序列；依次重復(fù)，直至就干更小的子序列；依次重復(fù)，直至就每個子序列對最低位關(guān)鍵字每個子序列對最低位關(guān)鍵字kd排序排序；最后將所有子序列依次連接在一起；最后將所有子序列依次連接在一起成為一個有序序列成為一個有序序列最低位優(yōu)先法最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字：從最低位關(guān)鍵字kd起起進行排序，然后再對高一位的關(guān)鍵字排序，進行排序，然后再對高一位的關(guān)鍵字排序，依次重復(fù)，直至對最高位關(guān)鍵字依次重復(fù)，直至對最高位關(guān)鍵字k1排序排序后，便成為一個有序序列后，便成為一個有序序列MSD與與LSD不同特點不同特點按按MSD排序，必須將序列逐層分割排序，必須將序列逐層分割成若干子序列，

5、然后對各子序列分別成若干子序列，然后對各子序列分別排序排序按按LSD排序，不必分成子序列，對每排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干且可不通過關(guān)鍵字比較，而通過若干次分配與收集實現(xiàn)排序次分配與收集實現(xiàn)排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序u基數(shù)排序：借助基數(shù)排序：借助“分配分配”和和“收集收集”對單邏輯關(guān)鍵字進行排序?qū)芜壿嬯P(guān)鍵字進行排序的一種方法的一種方法u鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序結(jié)構(gòu)的基數(shù)排序u鏈?zhǔn)交鶖?shù)排序步驟鏈?zhǔn)交鶖?shù)排序步驟設(shè)置設(shè)置10個隊列，個隊列，fi和和ei分別為第分

6、別為第i個隊列個隊列的頭指針和尾指針的頭指針和尾指針第一趟分配對最低位關(guān)鍵字（個位）進行第一趟分配對最低位關(guān)鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配，改變記錄的指針值，將鏈表中記錄分配至至10個鏈隊列中，每個隊列記錄的關(guān)鍵字個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同的個位相同第一趟收集是改變所有非空隊列的隊尾記第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將隊頭記錄，重新將10個隊列鏈成一個鏈表個隊列鏈成一個鏈表重復(fù)上述兩步，進行第二趟、第三趟分配重復(fù)上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位

7、進行，最后得和收集，分別對十位、百位進行，最后得到一個有序序列到一個有序序列例例初始狀態(tài)：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配00

8、8109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集： 內(nèi)部排序方法的選擇內(nèi)部排序方法的選擇各種排序方法各有優(yōu)缺點，故在不同情況下各種排序方法各有優(yōu)缺點，故在不同情況下可作不同的選擇。通常需考慮的因素有：待可作不同的選擇。通常需考慮的因素有：待排序的記錄個數(shù)；記錄本身的大??；記錄的

9、排序的記錄個數(shù)；記錄本身的大小；記錄的鍵值分布情況等。鍵值分布情況等。 若待排序的記錄個數(shù)若待排序的記錄個數(shù)n較小時，可采用簡單較小時，可采用簡單排序方法。排序方法。 若若n 較大時，應(yīng)采用快速排序或堆排序。較大時，應(yīng)采用快速排序或堆排序。 若待排序的記錄已基本有序，可采用起泡若待排序的記錄已基本有序，可采用起泡排序。排序。 各種內(nèi)排序方法的比較和選擇各種內(nèi)排序方法的比較和選擇 一一 各種內(nèi)排序方法的比較各種內(nèi)排序方法的比較1從時間復(fù)雜度比較從時間復(fù)雜度比較從平均時間復(fù)雜度來考慮，直接插入排序、冒泡排序、直接選擇排序是三種簡單的排序方法，時間復(fù)雜度都為O(n2)，而快速排序、堆排序、二路歸并排

10、序的時間復(fù)雜度都為O(nlog2n)，希爾排序的復(fù)雜度介于這兩者之間。若從最好的時間復(fù)雜度考慮，則直接插入排序和冒泡排序的時間復(fù)雜度最好，為O(n)，其它的最好情形同平均情形相同。若從最壞的時間復(fù)雜度考慮，則快速排序的為O(n2)，直接插入排序、冒泡排序、希爾排序同平均情形相同，但系數(shù)大約增加一倍，所以運行速度將降低一半，最壞情形對直接選擇排序、堆排序和歸并排序影響不大。2從空間復(fù)雜度比較從空間復(fù)雜度比較歸并排序的空間復(fù)雜度最大，為O(n)，快速排序的空間復(fù)雜度為O(log2n)，其它排序的空間復(fù)雜度為O（1）。 3.從穩(wěn)定性比較直接插入排序、冒泡排序、歸并排序是穩(wěn)定的排序方法，而直接選擇排序

11、、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。4從算法簡單性比較從算法簡單性比較直接插入排序、冒泡排序、直接選擇排序都是簡單的排序方法，算法簡單，易于理解，而希爾排序、快速排序、堆排序、歸并排序都是改進型的排序方法，算法比簡單排序要復(fù)雜得多，也難于理解。 二二 各種內(nèi)排序方法的選擇各種內(nèi)排序方法的選擇1從時間復(fù)雜度選擇從時間復(fù)雜度選擇對元素個數(shù)較多的排序，可以選快速排序、堆排序、歸并排序，元素個數(shù)較少時，可以選簡單的排序方法。2從空間復(fù)雜度選擇從空間復(fù)雜度選擇盡量選空間復(fù)雜度為O（1）的排序方法，其次選空間復(fù)雜度為O(log2n)的快速排序方法，最后才選空間復(fù)雜度為O（n）二路歸并排序的排序

12、方法。 3一般選擇規(guī)則一般選擇規(guī)則（1） 當(dāng)待排序元素的個數(shù)n較大，排序碼分布是隨機，而對穩(wěn)定性不做要求時，則采用快速排序為宜。（2)當(dāng)待排序元素的個數(shù)n大，內(nèi)存空間允許，且要求排序穩(wěn)定時，則采用二路歸并排序為宜。（3）當(dāng)待排序元素的個數(shù)n大，排序碼分布可能會出現(xiàn)正序或逆序的情形，且對穩(wěn)定性不做要求時，則采用堆排序或二路歸并排序為宜。（4)當(dāng)待排序元素的個數(shù)n小，元素基本有序或分布較隨機，且要求穩(wěn)定時，則采用直接插入排序為宜。 (5)當(dāng)待排序元素的個數(shù)n小，對穩(wěn)定性不做要求時，則采用直接選擇排序為宜，若排序碼不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。 比比較較次次數(shù)數(shù) 移移動動

13、次次數(shù)數(shù)附附加加存存儲儲排排 序序 方方 法法最最好好最最差差最最好好最最差差穩(wěn)穩(wěn)定定 性性最最好好最最差差直直接接插插入入排排序序nn2 0n2 1折折半半插插入入排排序序n log2n 0n2 1起起泡泡排排序序nn2 0n2 1快快速速排排序序nlog2nn2n log2nn2 log2nn2簡簡單單選選擇擇排排序序n2 0n 1錦錦標(biāo)標(biāo)賽賽排排序序n log2nn log2n n堆堆排排序序n log2nn log2n 1歸歸并并排排序序n log2nn log2n n內(nèi)部排序方法的比較內(nèi)部排序方法的比較當(dāng)當(dāng)n很大時用線性鏈表代替數(shù)組來排序很大時用線性鏈表代替數(shù)組來排序排序方法排序方法 最壞時間最壞時間 平均時間平均時間輔助存