[計(jì)算機(jī)軟件及應(yīng)用]第八章排序-資料下載頁(yè)
2024-10-16 23:21本頁(yè)面
【正文】 分成有次序的四堆，每一堆的牌均有相同的“花色”，然后分別對(duì)每一堆按“面值”大小整理有序。 也可采用另一種辦法 :先按不同“面值”分成 13堆，然后將這 13堆牌自小至大疊在一起（“ 3”在“ 2”之上，“ 4”在“ 3”之上， …… ，最上面的是 4張“ A”）， 然后將這付牌整個(gè)顛倒過(guò)來(lái)再按不同“花色”分成 4堆，最后將這 4堆牌按自小至大的次序合在一起（ 在最下面，在最上面），此時(shí)同樣得到一付滿足如上次序的牌。 這兩種整理?yè)淇伺频姆椒ū闶莾煞N多關(guān)鍵字的排序方法。 為了實(shí)現(xiàn)多關(guān)鍵字排序，通常有兩種方法 : 第一種方法是先對(duì)最高位關(guān)鍵字 K0進(jìn)行排序，將序列分成若干子序列，每個(gè)子序列中的記錄都具有相同的 K0值，然后分別對(duì)每個(gè)子序列按次高位關(guān)鍵字 K1進(jìn)行排序，按 K1值不同再分成若干個(gè)更小的子序列，每個(gè)子序列中的記錄都具有相同的 K1值，依次重復(fù)，直至完成對(duì) Kd1進(jìn)行排序，最后將所有子序列依次連接在一起成為一個(gè)有序序列，這種方法稱之為 最高位優(yōu)先 （ Most Significant Digit First）法，簡(jiǎn)稱 MSD法 。 第二種方法是從最低位關(guān)鍵字 Kd1起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字 Kd2進(jìn)行排序，依次重復(fù)，直到對(duì) K0進(jìn)行排序后便成為一個(gè)有序序列。這種方法稱之為 最低位優(yōu)先（ Least Siginifiˉcant Digit First）法，簡(jiǎn)稱 LSD法 。 基數(shù)排序 基數(shù)排序 MSD和 LSD只規(guī)定按什么樣的“關(guān)鍵字次序”來(lái)進(jìn)行排序，而未規(guī)定對(duì)每個(gè)關(guān)鍵字進(jìn)行排序時(shí)所用的方法，比較這兩種方法， LSD要比 MSD簡(jiǎn)單，因?yàn)?LSD是對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序，通過(guò)若干次“ 分配 ”和“ 收集 ”來(lái)實(shí)現(xiàn)排序，執(zhí)行的次數(shù)取決于 d的大小 。而 MSD需要處理各序列與子序列的獨(dú)立排序問(wèn)題，通常是一個(gè)遞歸問(wèn)題。 鏈?zhǔn)交鶖?shù)排序 基數(shù)排序是借助于多關(guān)鍵字排序思想進(jìn)行排序的方法，其基本操作是按關(guān)鍵字位進(jìn)行“分配”和“收集”。 在基數(shù)排序的“分配”與“收集”操作過(guò)程中，為了避免數(shù)據(jù)元素的大量移動(dòng)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)待排序的記錄序列。 基數(shù)排序 通常將關(guān)鍵字取值的數(shù)目稱為 基數(shù) ，用 RADIX表示，按 LSD進(jìn)行排序，對(duì)待排序的記錄序列按照復(fù)合關(guān)鍵字從低位到高位的順序交替地“分配”到 RADIX個(gè)隊(duì)列中后再“收集”，如此重復(fù) d次，最終得到有序的記錄序列。 有些記錄的關(guān)鍵字可以看成是由若干個(gè)關(guān)鍵字組合而成。即 K=K0K1 ...Kd1。 每個(gè)關(guān)鍵字 Ki表示關(guān)鍵字的一位，其中 K0為最高位，Kd1為最低位， d為關(guān)鍵字的位數(shù)。 基數(shù)排序 下面舉例說(shuō)明基數(shù)排序過(guò)程。設(shè)待排序記錄的關(guān)鍵字為 : 387， 456， 592， 625， 076， 471， 050， 396， 557，522 基數(shù)排序 基數(shù)排序 基數(shù)排序 ? 從基數(shù)排序的算法中容易看出，對(duì)于 n個(gè)記錄（假設(shè)每個(gè)記錄含 d個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字的取值范圍為 r），則采用基數(shù)排序需進(jìn)行 d趟關(guān)鍵字的分配和收集，每趟運(yùn)算時(shí)間復(fù)雜度為 O（ n+r），所以基數(shù)排序的時(shí)間復(fù)雜度為 O（ d（ n+r）） 。 ? 由于 d、 r是常數(shù)，當(dāng) n較大時(shí)，基數(shù)排序的時(shí)間復(fù)雜度近似為 O（ n）。但 n較小， d較大時(shí)，采用基數(shù)排序并不合 適 。只有當(dāng) n較大、 d較小時(shí)，基數(shù)排序才最為有效。 ? 這種排序方法的缺點(diǎn)是占用的存儲(chǔ)空間較多，每個(gè)待排序的記錄都需要加上指針域。 ? 基數(shù)排序是穩(wěn)定的 排序 算法。 基數(shù)排序 幾種排序方法的比較 1. 時(shí)間復(fù)雜度 ? 直接插入排序、簡(jiǎn)單選擇排序和冒泡排序這三種排序方法的時(shí)間復(fù)雜度均為 O（ n2），所以適用 n較小的情況。 ? 堆排序和歸并排序這兩種排序方法的時(shí)間復(fù)雜度為 O（ n log2n），快速排序方法的平均時(shí)間復(fù)雜度也為 O（ nlog2n），但快速排序在最壞情況下的時(shí)間復(fù)雜度為 O（ n2）。 ? 希爾排序方法的時(shí)間復(fù)雜度介于 O（ nlog2n）與 O（ n2）之間，基數(shù)排序方法的時(shí)間復(fù)雜度為 O（ d（ n+r）），基數(shù)排序適用于關(guān)鍵字位數(shù)較少而 n值很大的情況。 2. 空間復(fù)雜度 ? 歸并排序的空間復(fù)雜度最差，為 O（ n） 。 ? 快速排序的空間復(fù)雜度為 O（ log2n）（實(shí)現(xiàn)遞歸算法所需的?？臻g） 。 ? 基數(shù)排序的空間復(fù)雜度為 O（ 2r） 。 ? 其他排序方法的空間復(fù)雜度均為 O（ 1）。 幾種排序方法的比較 3. 穩(wěn)定性 直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的，而希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的。 綜上所述，在所介紹的幾種排序方法中，沒(méi)有哪一種是絕對(duì)最優(yōu)的。有的適用于 n較大的情況，有的適用于 n較小的情況。因此，在使用時(shí)需根據(jù)不同情況適當(dāng)選用，甚至可將多種方法結(jié)合起來(lái)使用。 幾種排序方法的比較 1. 排序是將一組數(shù)據(jù)按照一定的規(guī)律順序排列起來(lái)。排序方法有 內(nèi)部排序和 外部排序 ，內(nèi)部排序指待排序記錄在內(nèi)存中進(jìn)行的排序過(guò)程。外部排序指在排序過(guò)程中還需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。 2. 內(nèi)部排序的排序方法有 :插入排序、交換排序、選擇排序、歸并排序 和基數(shù)排序 。每種排序方法的排序過(guò)程及其排序思想各不相同，根據(jù)不同的場(chǎng)合選擇不同的排序方法。 3. 排序的穩(wěn)定性方面 :直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定 的，希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是 不穩(wěn)定 的。 本章小結(jié) 4. 排序方法的時(shí)間復(fù)雜度分別為 :直接插入排序、簡(jiǎn)單選擇排序和冒泡排序這三種排序方法的時(shí)間復(fù)雜度均為 O（ n2） ，堆排序和歸并排序這兩種排序方法的時(shí)間復(fù)雜度為 O（ nlog2n） ，快速排序方法的平均時(shí)間復(fù)雜度也為 O（ n log2n） ，但快速排序在最壞情況下的時(shí)間復(fù)雜度為 O（ n2） 。希爾排序方法的時(shí)間復(fù)雜度介于 O（ n log2n）與 O（ n2）之間 ，基數(shù)排序方法的時(shí)間復(fù)雜度為 O（ d（ n+r）） 。排序方法的空間復(fù)雜度分別為 :歸并排序的空間復(fù)雜度最差，為 O（ n） ?？焖倥判虻目臻g復(fù)雜度為 O（ log2n） 。基數(shù)排序的空間復(fù)雜度為 O（ 2r） 。其他排序方法的空間復(fù)雜度均為 O（ 1） 。 本章小結(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1