分治思想以及排序算法

《分治思想以及排序算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、分治思想以及排序算法2009/04/28內(nèi)容分治思想分治排序算法文件直接存取技術(shù)2作業(yè)講評從索引進(jìn)行二分檢索操作函數(shù)指針345文件直接存取6文件直接存?。≧andomFileAccess）fseek(fileName,offset,origin)…filestreamFile*fp;7RandomFileAccessrewind()resetsthecurrentpositiontothestartofthefilerewind(inFile)fseek()allowstheprogrammertomovetoanypositioninthefilefseek

2、(fileName,offset,origin)Origin:SEEK_SET,SEEK_CUR,andSEEK_ENDftell()returnstheoffsetvalueofthenextcharacterthatwillbereadorwrittenftell(inFile);8910排序算法：為什么要排序？有序表的優(yōu)點？缺點？構(gòu)造關(guān)系。按照什么原則排序？比較？如何進(jìn)行排序？11基本概念排序（Sorting）：簡單地說，排序就是把一組記錄按照某個（或某幾個）字段的值以遞增（由小到大）或遞減（由大到?。┑拇涡蛑匦屡帕械倪^程。（如按年齡從小到大排序）學(xué)號姓

3、名年齡性別2004001張佳18男2004002王鵬19男2004003劉寧17女2004004李娟18女2004005陳濤19男2004006李小燕18女12作為比較基礎(chǔ)的一個(或多個)字段，稱為排序碼。排序碼可以是數(shù)值、符號或符號串。排序碼不一定是關(guān)鍵碼，關(guān)鍵碼可以作為排序碼。關(guān)鍵碼是唯一的，但排序碼不一定唯一。排序碼不唯一時，排序的結(jié)果可能不唯一。參與排序的對象，稱為記錄。一個記錄可以包含多個字段。如果記錄集合中存在多個排序碼相同的記錄，經(jīng)過排序后，排序碼相同的記錄的前后次序保持不變，則這種排序方法稱為是穩(wěn)定的，否則是不穩(wěn)定的。排序碼與關(guān)鍵碼（prima

4、rykey）13排序方法可以分為五種∶插入排序、選擇排序、交換排序、分配排序和歸并排序。在排序過程中，全部記錄存放在內(nèi)存，則稱為內(nèi)排序，如果排序過程中需要使用外存，則稱為外排序。本章側(cè)重討論內(nèi)排序的方法，但有些方法(特別是歸并排序的思想)也可以用于外排序。排序的類型14排序算法的評價評價排序算法好壞的標(biāo)準(zhǔn)執(zhí)行算法所需的時間執(zhí)行算法所需要的附加空間算法本身的復(fù)雜程度也是考慮的一個因素排序的時間開銷是算法好壞的最重要的標(biāo)志排序的時間開銷衡量標(biāo)準(zhǔn):算法執(zhí)行中的比較次數(shù)（必須）。算法執(zhí)行中的移動次數(shù)（有可能避免）。通常會關(guān)注最壞情況和平均情況的開銷。15插入排序選擇排

5、序：直接選擇排序交換排序歸并排序直接插入排序二分插入排序起泡排序快速排序表插入排序Shell排序堆排序排序算法16插入排序基本思想：每步將一個待排序的記錄，按其排序碼大小插到前面已經(jīng)排序的字序列的合適位置，直到全部插入排序完為止。x順次選取一個元素插入到合適位置17插入排序的細(xì)分類如何插入到已排好序的序列中？直接插入（從后向前找位置后插入）O(n2)二分法插入（按二分法找位置后插入）O(nlog2n)表插入排序（按鏈表查找位置后插入）O(n2)18直接插入排序基本思想：假定前面m個元素已經(jīng)排序；取第(m+1)個元素，插入到前面的適當(dāng)位置；一直重復(fù)，到m=n為止

6、。（初始情況下，m=1）19第一趟：{23}，[起始只有一個記錄]{11,23}11第二趟：{11，23}，{11，23，55}55第三趟：{11，23，55}，{11，23，55，97}97第四趟：{11，23，55，97}，{11，19，23，55，97}19第五趟：{11，19，23，55，97}，{11，19，23，55，80，97}80示例：{23，11，55，97，19，80}20直接插入排序的算法中記錄的數(shù)據(jù)結(jié)構(gòu)typedefintKeyType;typedefintDataType;typedefstruct{KeyTypekey;/*排序碼字

7、段*/DataTypeinfo;/*記錄的其他字段*/}RecordNode;typedefstruct{intn;/*n為文件中的記錄個數(shù)，n

8、(n2)24直接插入排序算法評價4——