《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件6-14分配排序1

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：丁慧分配排序常州信息職業(yè)技術(shù)學(xué)院03分配排序分配排序的基本思想：排序過(guò)程無(wú)須比較關(guān)鍵字，而是通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序。一、箱排序1基本思想 箱排序的基本思想是：設(shè)置若干個(gè)箱子，依次掃描待排序的記錄R0,R1, Rn-1，把關(guān)鍵字等于k的記錄全都裝入到第k個(gè)箱子里（稱(chēng)為分配），然后按序號(hào)依次將各非空的箱子首尾連接起來(lái)（稱(chēng)為收集）。三、鏈表的插入04分配排序2箱排序說(shuō)明（1）箱排序中，箱子的個(gè)數(shù)取決于關(guān)鍵字的取值范圍。若R0.n-1中關(guān)鍵字的取值范圍是0到m-1的整數(shù)，則必須設(shè)置m個(gè)箱子。因此箱排序要求關(guān)鍵字的類(lèi)型是有限類(lèi)型，否則可能要

2、無(wú)限個(gè)箱子。（2）箱子的類(lèi)型應(yīng)設(shè)計(jì)成鏈表為宜。 一般情況下每個(gè)箱子中存放多少個(gè)關(guān)鍵字相同的記錄是無(wú)法預(yù)料的，故箱子的類(lèi)型應(yīng)設(shè)計(jì)成鏈表為宜。三、鏈表的插入05實(shí)現(xiàn)方法2：若輸入的待排序記錄是以鏈表形式給出時(shí)，出隊(duì)操作可簡(jiǎn)化為是將整個(gè)箱子鏈表鏈接到輸出鏈表的尾部。這只需要修改輸出鏈表的尾結(jié)點(diǎn)中的指針域，令其指向箱子鏈表的頭，然后修改輸出鏈表的尾指針，令其指向箱子鏈表的尾即可。分配排序2箱排序說(shuō)明（3）為保證排序是穩(wěn)定的，分配過(guò)程中裝箱及收集過(guò)程中的連接必須按先進(jìn)先出原則進(jìn)行。實(shí)現(xiàn)方法1：每個(gè)箱子設(shè)為一個(gè)鏈隊(duì)列。當(dāng)一記錄裝入某箱子時(shí)，應(yīng)做入隊(duì)操作將其插入該箱子尾部；而收集過(guò)程則是對(duì)箱子做出隊(duì)操作，依

3、次將出隊(duì)的記錄放到輸出序列中。06分配過(guò)程的時(shí)間是O(n)；收集過(guò)程的時(shí)間為O(m) （采用鏈表來(lái)存儲(chǔ)輸入的待排序記錄）或O(m+n)。因此，箱排序的時(shí)間為O(m+n)。若箱子個(gè)數(shù)m的數(shù)量級(jí)為O(n)，則箱排序的時(shí)間是線(xiàn)性的，即O(n)。注意：箱排序?qū)嵱脙r(jià)值不大，僅適用于作為基數(shù)排序的一個(gè)中間步驟。分配排序3算法簡(jiǎn)析07 桶排序是箱排序的變種，只是關(guān)鍵字的取值范圍必須是0,1)上的實(shí)數(shù)。為了區(qū)別于上述的箱排序，姑且稱(chēng)它為桶排序。 把0,1)劃分為n個(gè)大小相同的子區(qū)間，每一子區(qū)間是一個(gè)桶。然后將n個(gè)記錄分配到各個(gè)桶中。因?yàn)殛P(guān)鍵字序列是均勻分布在0,1)上的，所以一般不會(huì)有很多個(gè)記錄落入同一個(gè)桶中

4、。由于同一桶中的記錄其關(guān)鍵字不盡相同，所以必須采用關(guān)鍵字比較的排序方法（通常用插入排序）對(duì)各個(gè)桶進(jìn)行排序，然后依次將各非空桶中的記錄連接（收集）起來(lái)即可。分配排序二、 桶排序（Bucket Sort）1排序方法08分配排序 設(shè)R0.9中的關(guān)鍵字為（0.78，0.17，0.39，0.26，0.72，0.94，0.21，0.12，0.23，0.68）對(duì)其進(jìn)行桶排序的排序過(guò)程：第1步：分配。將各記錄按關(guān)鍵字的值分配到相應(yīng)的桶Bi中，如果在同一個(gè)桶中有多個(gè)記錄，使用直接插入排序按由小到大的順序排好序；第2步：收集。將B0到B9中非空桶中的記錄依次放入R0.9中，得到（0.12，0.17，0.21，0.

5、23，0.26，0.39，0.72，0.78，0.68，0.94），桶排序結(jié)束。01234567890.120.170.210.230.260.390.680.940.780.72B三、鏈表的插入09分配排序2桶排序算法#define m 10 /m表示桶的個(gè)數(shù)void BucketSort(SeqList R) /對(duì)R0.n-1做桶排序，假設(shè)Ri.key均是小于100的非負(fù)整數(shù) RecType Bmn; /Bi為第i個(gè)桶（0im），用于存放十位為i的記錄 int i,k,p=1,jm=0; /ji為計(jì)數(shù)器，用來(lái)記錄桶Bi中記錄的個(gè)數(shù) for(i=1;i=n;i+) /分配過(guò)程BRi.key/

6、10+jRi.key/10=Ri; /從BRi.key/101開(kāi)始存放 for(i=0;i0) InsertSort(Bi,ji); /桶Bi非空 for(i=0;i0) for(k=1;k=ji;k+,p+) Rp=Bik;10 桶排序的穩(wěn)定性與桶內(nèi)所選排序方法有關(guān)，如果桶內(nèi)所選排序方法是穩(wěn)定的，那么桶排序方法就是穩(wěn)定的，如果桶內(nèi)所選排序方法是不穩(wěn)定的，那么桶排序方法就是不穩(wěn)定的。分配排序3桶排序算法分析（1）時(shí)間性能 桶排序在平均情況下，即每個(gè)桶均勻分布n/m條記錄，時(shí)間復(fù)雜度是O(n2/m)；在最好情況下，即每個(gè)桶只有一條記錄，時(shí)間復(fù)雜度是線(xiàn)性的，即O(n)；但在最壞情況下，即n條記錄全落入了同一個(gè)桶，時(shí)間復(fù)雜度是O(n