算法與數(shù)據(jù)結(jié)構(gòu)(c語言) 第8章 排序

《算法與數(shù)據(jù)結(jié)構(gòu)(c語言) 第8章 排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第八章排序目錄8.1基本概念8.2插入排序8.2.1直接插入排序8.2.2二分法插入排序8.2.3表插入排序8.2.4Shell排序8.3選擇排序8.3.1直接選擇排序8.3.2堆排序8.4交換排序8.4.1起泡排序8.4.2快速排序8.5分配排序8.5.1概述8.5.2基數(shù)排序8.6歸并排序8.6.1內(nèi)排序8.6.2外排序*8.1基本概念排序的對象是由一組記錄組成的文件，每個(gè)記錄由若干字段組成，所謂排序碼是記錄中的一個(gè)(或多個(gè))字段，排序以排序碼為依據(jù)。排序碼可以不是關(guān)鍵碼，則可能有多個(gè)記錄具有相同的排序碼，使得排序的結(jié)果不唯一。排序碼之間需要進(jìn)行比較，本章中都假設(shè)

2、排序碼為整型。設(shè){R0,R1,…,Rn-1}是由n個(gè)記錄組成的文件，{K0,K1,…,Kn-1}是排序碼集合，所謂排序就是將文件中的全部記錄按排序碼不增(或不減)的次序重新排列。排序看成字典上的操作在排序的討論中，并不關(guān)心被排序?qū)ο蟊旧淼倪壿嫿Y(jié)構(gòu)，所以讀者可以把排序看成是字典上的一種操作。不同的排序算法，可能依賴與不同的存儲(chǔ)結(jié)構(gòu)，可以理解為在字典的不同存儲(chǔ)表示上排序的實(shí)現(xiàn)。而把非字典結(jié)構(gòu)中元素的排序，歸結(jié)為是對于其結(jié)點(diǎn)按照排序碼建立的密集索引的排序。與上一章關(guān)于索引的討論類似，在本章的具體排序算法中，只關(guān)心排序碼的作用和表示，而把記錄中的其它字典隱藏起來。在待排序的文

3、件中，如果存在多個(gè)排序碼相同的記錄，經(jīng)過排序后，相同排序碼記錄的相對次序如果保持不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。穩(wěn)定性本章中提到的記錄和文件，主要是指內(nèi)存的數(shù)據(jù)。待排序的記錄在排序過程中全部存放在內(nèi)存的稱為內(nèi)排序，否則稱為外排序。外排序也就是外存文件的排序。本章討論的主要是內(nèi)排序的方法，但有些方法(例如歸并排序)也適用于外排序。內(nèi)排序與外排序排序方法分類插入排序、選擇排序、交換排序、分配排序、歸并排序。（每一種方法具體可能有多個(gè)不同算法）評價(jià)排序算法代價(jià)的標(biāo)準(zhǔn)第一，執(zhí)行算法所需的時(shí)間；比較次數(shù)、移動(dòng)次數(shù)第二，執(zhí)行算法所需要的附加空間；另外，算法本身的復(fù)

4、雜程度也是比較算法一個(gè)因素。8.2插入排序基本方法是∶每步將一個(gè)待排序的記錄，按其排序碼大小，插到前面已經(jīng)排序的文件中的適當(dāng)位置，直到全部插入完為止。直接插入排序二分法插入排序表插入排序shell排序8.2.1直接插入排序假設(shè)待排序的n個(gè)記錄{R0,R1,…,Rn-1}順序存放在數(shù)組中，直接插入法在插入記錄Ri(i=1,2…n-1)時(shí)，記錄集合被劃分為兩個(gè)區(qū)間[R0，Ri-1]和[Ri，Rn-1]，其中，前一個(gè)子區(qū)間已經(jīng)排好序，后一個(gè)子區(qū)間是當(dāng)前未排序的部分，將排序碼Ki與Ki-1，Ki-2，…，K0依次比較，找出應(yīng)該插入的位置，將記錄Ri插入。直接插入排序采用順序存

5、儲(chǔ)結(jié)構(gòu)。例題設(shè)待排序的記錄共8個(gè)，排序碼分別為49,38,65,97,76,13,27,49’，請用直接插入排序法排序(為了區(qū)別兩個(gè)相同的排序碼49，后面的49用49’表示)。初始序列∶[49]38659776132749’i=1∶[3849]659776132749’i=2∶[384965]9776132749’i=3∶[38496597]76132749’i=4∶[3849657697]132749’i=5∶[133849657697]2749’i=6∶[13273849657697]49’i=7∶[1327384949’657697]typedefi

6、ntKeyType;typedefintDataType;typedefstruct{KeyTypekey;/*排序碼字段*/DataTypeinfo;/*記錄的其它字段*/}RecordNode;typedefstruct{intn;/*n為文件中的記錄個(gè)數(shù)*/RecordNode*record;}SortObject;存儲(chǔ)結(jié)構(gòu)程序?qū)崿F(xiàn)：voidinsertSort(SortObject*pvector)若文件初態(tài)為正序，則算法的時(shí)間復(fù)雜度為O(n)，若初態(tài)為反序，則時(shí)間復(fù)雜度為O(n2)。平均移動(dòng)次數(shù)與平均比較次數(shù)同級(jí)，是O(n2)。直接插入排序的平均時(shí)間復(fù)雜度為

7、T(n)=O(n2)。算法中引入了一個(gè)附加的記錄空間temp，因此輔助空間為S(n)=O(1)。直接插入排序是穩(wěn)定的。算法的設(shè)計(jì)與分析8.2.2二分法插入排序在直接插入排序的基礎(chǔ)上減少比較的次數(shù)，即在插入Ri時(shí)改用二分法比較找插入位置，便得到二分法插入排序。(1)[13273849657697]49’(2)13273849[657697]49’(3)13273849[65]769749’(4)1327384949’657697二分法插入排序示例二分法插入排序必須采用順序存儲(chǔ)方式，存儲(chǔ)結(jié)構(gòu)的定義同上一節(jié)的SortObject。程序?qū)崿F(xiàn)存儲(chǔ)結(jié)構(gòu)與算法代價(jià)