C語(yǔ)言程序設(shè)計(jì)(清華鄭莉安潁蓮)chap7

1、C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 1第七講第七講 查找與排序算法查找與排序算法參考書(shū)：參考書(shū)：計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)第十章第十章 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C C語(yǔ)言版）語(yǔ)言版）第九章第九章C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 2本講主要內(nèi)容本講主要內(nèi)容 排序算法排序算法- 直接插入排序直接插入排序- 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序- 起泡法排序起泡法排序 查找算法查找算法- 順序查找順序查找- 折半查找折半查找C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 3排序排序 排序排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)它的功能是將

2、一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素的任意序列，重新排的任意序列，重新排列成一個(gè)按列成一個(gè)按關(guān)鍵字關(guān)鍵字有序的序列。有序的序列。- 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。組成。- 關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素。識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素。C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 4內(nèi)部排序與外部排序內(nèi)部排序與外部排序 內(nèi)部排序：內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)待排序的數(shù)據(jù)元素存放

3、在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過(guò)程。存中進(jìn)行的排序過(guò)程。 外部排序：外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過(guò)程內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 5內(nèi)部排序方法內(nèi)部排序方法 插入排序插入排序- 將一個(gè)待排序序列的元素，逐個(gè)按其關(guān)鍵字的大小將一個(gè)待排序序列的元素，逐個(gè)按其關(guān)鍵字的大小插入到前面已排好的有序序列的適當(dāng)位置上，直到插入到前面已排好的有序序列的適當(dāng)位置上，直到待排序元素全部插入完為止。待排序元素全部插入完為止。

4、選擇排序選擇排序- 每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。序列的最后，直至全部排完。 交換排序交換排序- 兩兩比較待排序序列中的元素，并交換不滿足順序兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)記錄，直到全部滿足順序要求為止。要求的各對(duì)記錄，直到全部滿足順序要求為止。C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 6直接插入排序直接插入排序在插入類排序方法中，因?qū)ふ也迦胛恢玫姆椒ú煌?，又分為不同的插入排序方法，其中最?jiǎn)單的是

5、：直接插入排序。下面舉例說(shuō)明：初始狀態(tài)：初始狀態(tài)： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 4 4 4 5 10 20 12 34 5 10 20 12 32 2 1010 4 5 10 20 12 34 5 10 20 12 33 3 2020 4 5 10 20 12 34 5 10 20 12 34 4 1212 4 5 10 12 20 34 5 10 12 20 35 5 33 3 4 5 10 12 203 4 5 10 12 20C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 7簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序在選擇類排序方法中，從待排序序列中選

6、擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是：簡(jiǎn)單選擇排序。下面舉例說(shuō)明：5 4 10 20 12 5 4 10 20 12 3 3 初始狀態(tài)：初始狀態(tài)：3 3 4 4 10 20 12 5 10 20 12 53 4 10 20 12 3 4 10 20 12 5 5 第 i i 次選擇后，將選出的那個(gè)記錄與第 i i 個(gè)記錄做交換交換。3 4 5 20 12 3 4 5 20 12 1010 . .C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 8起泡排序起泡排序最簡(jiǎn)單的交換排序方法起泡排序?qū)哂衝個(gè)元素的序列按升序進(jìn)行起泡排序的步驟：首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為

7、逆序，則將兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第n-1和第n個(gè)元素進(jìn)行了比較和交換。此過(guò)程稱為第一趟起泡排序。經(jīng)過(guò)第一趟，最大的元素便被交換到第n個(gè)位置。對(duì)前n-1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個(gè)位置。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì)n個(gè)元素的序列，起泡排序最多需要進(jìn)行n-1趟。C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 9起泡排序舉例起泡排序舉例對(duì)整數(shù)序列對(duì)整數(shù)序列 8 5 2 4 3 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐

8、漸上升每趟沉下一個(gè)最大的C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 10查找查找 查找查找- 所謂查找，就是在一個(gè)數(shù)據(jù)元素的集合中，按照某種方式所謂查找，就是在一個(gè)數(shù)據(jù)元素的集合中，按照某種方式找出所需要的特定數(shù)據(jù)元素的過(guò)程。找出所需要的特定數(shù)據(jù)元素的過(guò)程。 兩種最簡(jiǎn)單的查找方法：兩種最簡(jiǎn)單的查找方法：- 順序查找順序查找從數(shù)據(jù)序列第一個(gè)元素開(kāi)始，將給定值逐個(gè)與各元素的關(guān)從數(shù)據(jù)序列第一個(gè)元素開(kāi)始，將給定值逐個(gè)與各元素的關(guān)鍵值比較，直到找到相等者。若找不到相等者，便是查找鍵值比較，直到找到相等者。若找不到相等者，便是查找不成功。不成功。- 折半查找（二分法查找）折半查找（二分法查找）對(duì)于已按關(guān)

9、鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分對(duì)于已按關(guān)鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。直至找到或找不到為止。C語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 11折半查找舉例折半查找舉例用折半查找法，在下列序列中查找值為用折半查找法，在下列序列中查找值為2121的元素：的元素：L=1513192137566475808892H=11M =INT(L+H)/2)=6513192137L=1H=M-1=5M=INT(L+H)/2)=3M2137HL=M+1=4LM=INT(L+H)/2)=4MC語(yǔ)言程序設(shè)計(jì)清華大學(xué) 鄭莉 安穎蓮Page 12查找與排序算法綜合應(yīng)用舉例查找與排序算法綜合應(yīng)用舉例 題目：使用前面介紹的三種排序、兩種查找算題目：使用前面介紹的三種排序、兩種查找算法，對(duì)若干人的姓名（字符串）進(jìn)行排序和查法，對(duì)若干人的姓名（字符串）進(jìn)行排序和查找。找。 編程要點(diǎn)：編程要點(diǎn)：- 查找、排序算法如前所述查找、排序算法如前所述- 對(duì)若干字符串進(jìn)行排序，為避免大量的數(shù)據(jù)交換，對(duì)若干字符串進(jìn)行排序，為避免大量的數(shù)據(jù)交換，應(yīng)使用指