第十章內(nèi)部排序

1、第十章 內(nèi)部排序主要內(nèi)容10.1 概述10.2 插入排序10.3 快速排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種內(nèi)部排序方法的比較討論排序概念 所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增增(或遞減減)次序排列起來(lái)。 NBA成績(jī)表；獎(jiǎng)學(xué)金評(píng)定綜合分；內(nèi)部排序內(nèi)部排序 外部排序外部排序 將欲處理的數(shù)據(jù)整個(gè)存放到內(nèi)部存將欲處理的數(shù)據(jù)整個(gè)存放到內(nèi)部存儲(chǔ)器中排序，數(shù)據(jù)可被隨機(jī)存取儲(chǔ)器中排序，數(shù)據(jù)可被隨機(jī)存取 交換式排序交換式排序 選擇式排序選擇式排序 插入式排序插入式排序 借助外部的輔助存儲(chǔ)器（比如：硬盤(pán)），由借助外部的輔助存儲(chǔ)器（比如：硬盤(pán)），由于數(shù)據(jù)是存在外存中

2、，故數(shù)據(jù)不可隨機(jī)被于數(shù)據(jù)是存在外存中，故數(shù)據(jù)不可隨機(jī)被存取存取 排序的分類(lèi)歸并排序歸并排序 基數(shù)排序基數(shù)排序 比較標(biāo)準(zhǔn) 空間復(fù)雜度 時(shí)間復(fù)雜度 穩(wěn)定性穩(wěn)定穩(wěn)定 不穩(wěn)定不穩(wěn)定 排序過(guò)后能使值相同的數(shù)據(jù)保排序過(guò)后能使值相同的數(shù)據(jù)保持原順序中的相對(duì)位置持原順序中的相對(duì)位置 排序過(guò)后不能使值相同的數(shù)據(jù)保持原順序排序過(guò)后不能使值相同的數(shù)據(jù)保持原順序493256492727324949562732494956基本操作大多數(shù)排序算法都有兩個(gè)基本的操作：比較兩個(gè)排序碼的大小；改變指向記錄的指針或移動(dòng)記錄本身。 注意： 第(2)種基本操作的實(shí)現(xiàn)依賴(lài)于待排序記錄的存儲(chǔ)方式。#define MAXSIZE 20 /

3、一個(gè)用作示例的小順序表的最大長(zhǎng)度一個(gè)用作示例的小順序表的最大長(zhǎng)度typedef int KeyType; /定義關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型定義關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型typedef struct KeyType key; /關(guān)鍵字關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng)RedType; /記錄類(lèi)型記錄類(lèi)型typedef struct RedType rMAXSIZE+1; /r0賦閑或用作哨兵單元賦閑或用作哨兵單元 int length; /順序表長(zhǎng)度順序表長(zhǎng)度SqList;10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希爾排序基本思想：基本思

4、想：順序順序地把待排序的數(shù)據(jù)元素按其值的大小地把待排序的數(shù)據(jù)元素按其值的大小插入插入到已排序數(shù)據(jù)元素子集合的到已排序數(shù)據(jù)元素子集合的適當(dāng)位置適當(dāng)位置有序序列有序序列無(wú)序序列無(wú)序序列一、直接插入排序12578630941256783094直接插入排序子集合的數(shù)據(jù)元素個(gè)數(shù)子集合的數(shù)據(jù)元素個(gè)數(shù)從從只有只有一一個(gè)個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素開(kāi)始開(kāi)始逐次逐次增大增大。當(dāng)當(dāng)子集合子集合大小大小等于等于原集合原集合時(shí)排序完畢。時(shí)排序完畢。直接插入排序 64647 789896 62424556464 89896 62424557 76464 6 62424557 764648989 242489895 57 7898

5、96 6初始序列初始序列: :第一次排序第一次排序: :第二次排序第二次排序: :第三次排序第三次排序: :556 67 764648989 2424第四次排序第四次排序: :556 67 724246464 第五次排序第五次排序: :Temp 6j896476jjj557 764648989 24246 6第三次排序第三次排序: :Temp 689647low6二、折半插入二、折半插入 基本思想：在 查找插入位置時(shí)，使用折半查找算法。mhigh 三、2-路插入排序 基本思想：增設(shè)同類(lèi)型數(shù)組d,視為循環(huán)向量。以d1為中心，原數(shù)列中比d1小的往前插，比d1大的往后插。 原數(shù)列：49 38 65

6、97 76 13 27 49 d數(shù)組： 49d1first final3865 97final76final13first27first9749final四、表插入排序key:49 38 65 97 76 13 27 49 基本思想：l 把待排序的數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；l 小組的個(gè)數(shù)逐次縮?。籰 當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程結(jié)束。l 希爾排序又稱(chēng)作縮小增量排序。 五、希爾排序增量序列為：增量序列為：5 5，3 3，1 1void ShellSort(SqList &L, int dlta ,int t) /按增量序列按增量序列dlt

7、a0.t-1對(duì)順序表對(duì)順序表L作希爾排序作希爾排序 for(k=0; kai+1，則交換兩個(gè)數(shù)據(jù)元素，否則不交換。 當(dāng)完成一趟交換以后，最大的元素將會(huì)出現(xiàn)在數(shù)組的最后一個(gè)位置。1.依次重復(fù)以上過(guò)程，當(dāng)?shù)趎-1趟結(jié)束時(shí)，n個(gè)數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a1中，a0中放置了最小的數(shù)據(jù)元素。起泡排序493865977613279797973849271376653849276513384927133849271338271376766549382713特點(diǎn)：特點(diǎn)：1.n個(gè)數(shù)排序共需進(jìn)行n-1趟比較2.第i趟共需要進(jìn)行n-i次比較void BubbleSort(SqList &L) for(

8、i=1;in; i+) change=FALSE; for(j=1; jL.rj+1.key) change=TRUE;L.rjL.rj+1; if(!change) return; 共進(jìn)行共進(jìn)行n-1n-1趟排序，趟排序，共進(jìn)行共進(jìn)行n(n-1)/2n(n-1)/2次比較次比較T(n)=O(nT(n)=O(n2 2) )二、快速排序算法思想：指定樞軸(通常為第一個(gè)記錄) 通過(guò)一趟排序?qū)⒁詷休S為中心，把待排記錄分割為獨(dú)立的兩部分，使得左邊左邊記錄的關(guān)鍵字小于小于樞軸值，右邊右邊記錄的關(guān)鍵字大于大于樞軸值1.對(duì)左右兩部分兩部分記錄序列重復(fù)上述過(guò)程，依次類(lèi)推，直到子序列中只剩下一個(gè)記錄或不含記錄為

9、止。27 38 13 49 76 97 65 4949 38 65 97 76 13 27 49i27 38 65 97 76 13 49 4927 38 49 97 76 13 65 49jiiijjijj27 38 13 97 76 49 65 49ijii j27 38 13jjlow=s; high=t; pivotkey=L.rlow.key;從high開(kāi)始往前找第一個(gè)關(guān)鍵字小于pivotkey的記錄，與樞軸記錄交換從low開(kāi)始往后找第一個(gè)關(guān)鍵字大于pivotkey的記錄，與樞軸記錄交換重復(fù)上述兩步直到low= =high為止1. 此時(shí)樞軸記錄所在的位置i=low=high27 38

10、 13 49 76 97 65 49T(n)=O(nlog2n)10.4 選擇排序一、直接選擇排序 基本思想：從待排序的數(shù)據(jù)元素集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置；1. 如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。 直接選擇排序149238365497576613727849ki=1jkjjjjkjjk1349直接選擇排序149238365497576613727849i=kjjjjjj1349k k2共進(jìn)行共進(jìn)行n-1趟排序，趟排序，n(

11、n-1)/2次比較次比較T(n)=O(n2)對(duì)對(duì)n個(gè)記錄的關(guān)鍵字兩兩比較，共進(jìn)行個(gè)記錄的關(guān)鍵字兩兩比較，共進(jìn)行n/2次，如此重復(fù)次，如此重復(fù)直到最后找出最小記錄，此過(guò)程可以用有直到最后找出最小記錄，此過(guò)程可以用有n個(gè)葉子的完全個(gè)葉子的完全二叉樹(shù)表示；二叉樹(shù)表示；將葉子結(jié)點(diǎn)中最小關(guān)鍵字改為將葉子結(jié)點(diǎn)中最小關(guān)鍵字改為MAXINT，然后該葉子與其，然后該葉子與其左左/右兄弟關(guān)鍵字比較，依次修改從葉子到根的路徑上各右兄弟關(guān)鍵字比較，依次修改從葉子到根的路徑上各結(jié)點(diǎn)的關(guān)鍵字值，結(jié)點(diǎn)的關(guān)鍵字值， 則根結(jié)點(diǎn)為次小記錄；則根結(jié)點(diǎn)為次小記錄；重復(fù)重復(fù)2，直到葉子結(jié)點(diǎn)均為，直到葉子結(jié)點(diǎn)均為MAXINT為止。為止。

12、a0a116211616632521212549251663950808082121 若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，把這個(gè)一維數(shù)若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，把這個(gè)一維數(shù)組看成是一棵完全二叉樹(shù)，則堆對(duì)應(yīng)的完全二叉樹(shù)中所有非組看成是一棵完全二叉樹(shù)，則堆對(duì)應(yīng)的完全二叉樹(shù)中所有非終端結(jié)點(diǎn)的值均大于或均小于其左右孩子的值。終端結(jié)點(diǎn)的值均大于或均小于其左右孩子的值。大大頂頂堆堆大大根根堆堆堆排序方法：堆排序方法：由一個(gè)無(wú)序的序列建成一個(gè)堆由一個(gè)無(wú)序的序列建成一個(gè)堆輸出堆頂?shù)淖钚≈递敵龆秧數(shù)淖钚≈凳Ｓ嗟脑亟ǔ梢粋€(gè)新的堆剩余的元素建成一個(gè)新的堆1. 1.重復(fù)重復(fù)2 2和和3 3093811

13、962783小小頂頂堆堆小小根根堆堆308547122436915349 38 65 97 76 13 27 49輸出輸出1313后后, ,用用序列中最后一序列中最后一個(gè)記錄代替根個(gè)記錄代替根結(jié)點(diǎn)結(jié)點(diǎn)篩篩選選為為堆頂元素與它的左右子樹(shù)根結(jié)點(diǎn)比較堆頂元素與它的左右子樹(shù)根結(jié)點(diǎn)比較l 若右子樹(shù)根若右子樹(shù)根 左子樹(shù)根左子樹(shù)根 堆頂堆頂 根結(jié)點(diǎn)與根結(jié)點(diǎn)與右子樹(shù)根右子樹(shù)根交換交換l 若左子樹(shù)根若左子樹(shù)根 右子樹(shù)根右子樹(shù)根 堆頂堆頂 根結(jié)點(diǎn)與根結(jié)點(diǎn)與左子樹(shù)根左子樹(shù)根交換交換這個(gè)從堆頂?shù)饺~子的調(diào)整過(guò)程稱(chēng)為這個(gè)從堆頂?shù)饺~子的調(diào)整過(guò)程稱(chēng)為篩選篩選1338497697276549973849762765492738

14、4976496597對(duì)一個(gè)無(wú)序序列建立堆也是篩選過(guò)程對(duì)一個(gè)無(wú)序序列建立堆也是篩選過(guò)程,篩選從篩選從n/2個(gè)記錄開(kāi)始。個(gè)記錄開(kāi)始。49 38 65 97 76 13 27 4976274913496538974997657649273813建立大頂堆建立大頂堆493865764927971349766549382797134997657649273813497665493827971349276549387697134965274938769713496527493876971349132749387697651349274938769765134927493876976549132749387

15、697654949273813769765494927381376976549132738497697654938271349769765建建大頂堆大頂堆，排序，排序結(jié)果為結(jié)果為從小到大從小到大493827134976976549273813497697654913382749769765T(n)=O(nlog2n)10.5 歸并排序 基本思想： 將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列; 然后進(jìn)行兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序序列; 再進(jìn)行兩兩歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列;1. 不斷重復(fù)歸并直至得到一個(gè)長(zhǎng)度為n的有序序列為止。歸并排序過(guò)程 (49) (38)

16、(65) (97) (76) (13) (27)(38 49) (38 49 65 97)(65 97)(13 76)(27) (13 27 38 49 65 76 97)(13 27 76)10.6 基數(shù)排序不通過(guò)關(guān)鍵字之間的比較進(jìn)行排序不通過(guò)關(guān)鍵字之間的比較進(jìn)行排序 一、多關(guān)鍵字排序一、多關(guān)鍵字排序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)(1,1),(

17、2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)排序思想排序思想 基數(shù)排序是按組成關(guān)鍵字的各位的值進(jìn)行分配和收集，與前面介紹的排序方法不同，它無(wú)需進(jìn)行關(guān)鍵字之間的比較。 設(shè)關(guān)鍵字有d 位，每位的取值范圍為 r (稱(chēng)為基數(shù))，則需要進(jìn)行d 趟分配與收集，需要設(shè)立 r 個(gè)隊(duì)列。 例如： 關(guān)鍵字是4位字符串，需要26個(gè)隊(duì)列，4趟分配與收集； 關(guān)鍵字3位十進(jìn)制數(shù)，需要10個(gè)隊(duì)列，3趟分

18、配與收集基數(shù)排序過(guò)程278109063930589184505269008083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 278pp109p063p930p589p184p505p269p008p083930063083184505278008109589269 505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 505008109930269063278589184083f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 008063083109184269278505589930008063183109184269278505589930930063083184505278008109589269 各種排序方法的比較各種排序方法的比較對(duì)排序算法應(yīng)該從以下幾個(gè)方面綜合考慮：對(duì)排序算法應(yīng)該從以下幾個(gè)方面綜合考慮：時(shí)間復(fù)雜性；時(shí)間復(fù)雜性；空間復(fù)雜性；空間復(fù)雜性；穩(wěn)定性；穩(wěn)定性；算法簡(jiǎn)單性；算法簡(jiǎn)單性；待排序記錄個(gè)數(shù)待排序記錄個(gè)數(shù)n的大?。坏拇笮?；記錄本身信息量的大小；記錄