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

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

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

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

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

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

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

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

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

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

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

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

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

13、次次數(shù)數(shù)附附加加存存儲(chǔ)儲(chǔ)排排 序序 方方 法法最最好好最最差差最最好好最最差差穩(wěn)穩(wěn)定定 性性最最好好最最差差直直接接插插入入排排序序nn2 0n2 1折折半半插插入入排排序序n log2n 0n2 1起起泡泡排排序序nn2 0n2 1快快速速排排序序nlog2nn2n log2nn2 log2nn2簡(jiǎn)簡(jiǎn)單單選選擇擇排排序序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ù)組來(lái)排序很大時(shí)用線性鏈表代替數(shù)組來(lái)排序排序方法排序方法 最壞時(shí)間最壞時(shí)間 平均時(shí)間平均時(shí)間輔助存