第十章內部排序

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

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

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

4、想：順序順序地把待排序的數(shù)據(jù)元素按其值的大小地把待排序的數(shù)據(jù)元素按其值的大小插入插入到已排序數(shù)據(jù)元素子集合的到已排序數(shù)據(jù)元素子集合的適當位置適當位置有序序列有序序列無序序列無序序列一、直接插入排序12578630941256783094直接插入排序子集合的數(shù)據(jù)元素個數(shù)子集合的數(shù)據(jù)元素個數(shù)從從只有只有一一個個數(shù)據(jù)元素數(shù)據(jù)元素開始開始逐次逐次增大增大。當當子集合子集合大小大小等于等于原集合原集合時排序完畢。時排序完畢。直接插入排序 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二、折半插入二、折半插入 基本思想：在 查找插入位置時，使用折半查找算法。mhigh 三、2-路插入排序 基本思想：增設同類型數(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ù)元素分成若干個小組，對同一小組內的數(shù)據(jù)元素用直接插入法排序；l 小組的個數(shù)逐次縮??；l 當完成了所有數(shù)據(jù)元素都在一個組內的排序后排序過程結束。l 希爾排序又稱作縮小增量排序。 五、希爾排序增量序列為：增量序列為：5 5，3 3，1 1void ShellSort(SqList &L, int dlta ,int t) /按增量序列按增量序列dlt

7、a0.t-1對順序表對順序表L作希爾排序作希爾排序 for(k=0; kai+1，則交換兩個數(shù)據(jù)元素，否則不交換。 當完成一趟交換以后，最大的元素將會出現(xiàn)在數(shù)組的最后一個位置。1.依次重復以上過程，當?shù)趎-1趟結束時，n個數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a1中，a0中放置了最小的數(shù)據(jù)元素。起泡排序493865977613279797973849271376653849276513384927133849271338271376766549382713特點：特點：1.n個數(shù)排序共需進行n-1趟比較2.第i趟共需要進行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; 共進行共進行n-1n-1趟排序，趟排序，共進行共進行n(n-1)/2n(n-1)/2次比較次比較T(n)=O(nT(n)=O(n2 2) )二、快速排序算法思想：指定樞軸(通常為第一個記錄) 通過一趟排序將以樞軸為中心，把待排記錄分割為獨立的兩部分，使得左邊左邊記錄的關鍵字小于小于樞軸值，右邊右邊記錄的關鍵字大于大于樞軸值1.對左右兩部分兩部分記錄序列重復上述過程，依次類推，直到子序列中只剩下一個記錄或不含記錄為

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開始往前找第一個關鍵字小于pivotkey的記錄，與樞軸記錄交換從low開始往后找第一個關鍵字大于pivotkey的記錄，與樞軸記錄交換重復上述兩步直到low= =high為止1. 此時樞軸記錄所在的位置i=low=high27 38

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

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

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

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

14、4976496597對一個無序序列建立堆也是篩選過程對一個無序序列建立堆也是篩選過程,篩選從篩選從n/2個記錄開始。個記錄開始。49 38 65 97 76 13 27 4976274913496538974997657649273813建立大頂堆建立大頂堆493865764927971349766549382797134997657649273813497665493827971349276549387697134965274938769713496527493876971349132749387697651349274938769765134927493876976549132749387

15、697654949273813769765494927381376976549132738497697654938271349769765建建大頂堆大頂堆，排序，排序結果為結果為從小到大從小到大493827134976976549273813497697654913382749769765T(n)=O(nlog2n)10.5 歸并排序 基本思想： 將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列; 然后進行兩兩歸并，得到n/2個長度為2的有序序列; 再進行兩兩歸并，得到n/4個長度為4的有序序列;1. 不斷重復歸并直至得到一個長度為n的有序序列為止。歸并排序過程 (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ù)排序不通過關鍵字之間的比較進行排序不通過關鍵字之間的比較進行排序 一、多關鍵字排序一、多關鍵字排序(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ù)排序是按組成關鍵字的各位的值進行分配和收集，與前面介紹的排序方法不同，它無需進行關鍵字之間的比較。 設關鍵字有d 位，每位的取值范圍為 r (稱為基數(shù))，則需要進行d 趟分配與收集，需要設立 r 個隊列。 例如： 關鍵字是4位字符串，需要26個隊列，4趟分配與收集； 關鍵字3位十進制數(shù)，需要10個隊列，3趟分

18、配與收集基數(shù)排序過程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 各種排序方法的比較各種排序方法的比較對排序算法應該從以下幾個方面綜合考慮：對排序算法應該從以下幾個方面綜合考慮：時間復雜性；時間復雜性；空間復雜性；空間復雜性；穩(wěn)定性；穩(wěn)定性；算法簡單性；算法簡單性；待排序記錄個數(shù)待排序記錄個數(shù)n的大??；的大小；記錄本身信息量的大??；記錄