數據結構與算法（C語言） 教案 第06章 查找與排序

千等教育

數據結構與算法（C語言篇）

教學設計

課程名稱：數據結構與算法rc語言篇）

授課年級：____________________________________

授課學期：____________________________________

教卵發(fā)名：____________________________________

2020年03月01日

計劃

課程名稱第6章查找與排序4學時

學時

內容分析本章主要介紹查找、排序

教學目標

要求學生掌握常用的查找算法、掌握常用的排序算法、掌握查找算法的

與

代碼編寫方法、掌握排序算法的代碼編寫方法

教學要求

教學重點查找、排序

教學難點查找、排序

教學方式課堂講解及ppt演示

第一課時

(查找、排序)

Q內容回顧

1.回顧上節(jié)內容，引出本課時主題。

上節(jié)已經介紹了章圖，本章將主要介紹算法中的常用操作一一查找與排

序。查找與排序作為數據處理的基本操作，是學習編程必須掌握的。查找是

在給定的數據集合(表)中搜索指定的數據元素。排序是將數據集合中的各

個數據元素按照指定的順序進行排列。查找與排序的算法很多，根據數據集

合的不同特點使用不同的查找與排序算法，可以節(jié)省空間與時間，提高程序

效率。本章將重點圍繞查找與排序算法的原理與代碼實現進行介紹。

2.明確學習目標

教(1)能夠掌握順序查找

(2)能夠掌握折半查找

學(3)能夠掌握分塊查找

(4)能夠掌握哈希查找

過(5)能夠掌握排序的概念

(6)能夠掌握直接插入排序

程(7)能夠掌握希爾排序

Q知識講解

＞順序查找

順序查找(SequentialSearch)又可以稱為線性查找，是最基本的查

找技術。順序查找的基本原理是從數據集合中的第一個(或最后一個)數據

元素開始，逐個與給定值進行對比。如果某個數據元素與給定值相同，則查

找成功。如果查找到最后一個(或第一個)數據元素，都與給定值不同，則

查找失敗。

順序查找算法比較簡單，以整型數據為例，代碼參考教材6.1.1節(jié)。

＞折半查找

當數據集合中的數據元素無序排列時，只能采用順序查找，而如果這個

數據集合中的數據元素是有序的，則可以采用折半查找來提高查找效率。

折半查找(BinarySearch)又稱為二分查找?折半查找的基本原理是

在有序的表中取中間的數據作為比較對象。如果查找的值與中間的值相等，

則查找成功；如果查找的值小于中間的值，則到有序表的左半區(qū)繼續(xù)查找；

如果查找的值大于中間的值，則到有序表的右半區(qū)繼續(xù)查找。不斷重復上述

步驟，直到查找成功，如圖所示。

14

"'給定值

lowvhigh

第一次折半

0123456789101112

131920

low?high

第二次折半

▼▼

0123456789101112

11：121314，5，6，7181920212223

查找成功

>分塊查找

分塊查找(BlockSearch)又稱為索引順序查找，是介于順序查找與折

半查找之間的查找算法，也是順序查找算法的一種改進算法。

分塊查找類似于從書籍中查找資料。假設讀者需要從一本書中查找資

料，一般的做法是先從目錄開始，找到資料所在章節(jié)的起始頁面，然后從該

起始頁向后尋找。這種做法明顯要比從書的第一頁向后查找快很多。因此，

書籍在編輯時，都會將所有的內容按照一定的規(guī)則分成若干塊(章)，每一

塊再分為若干個小塊(節(jié))，并設置它們的位置(頁)，形成一個目錄，通

過這個目錄即可實現快速查找。這個目錄就是索引表，這種查找方式就是分

塊查找。

分塊查找需要將數據集合分成若干個塊，并且這些塊滿足兩個條件。

(1)塊內無序，即每一塊中的數據不要求有序。

(2)塊間有序，即塊與塊之間是有序的。后一個塊中的各個數據元素都

比前一個塊中的任何數據元素大。例如，第一個塊中的數據元素都小于30,

那么第二個塊中的數據元素都必須大于等于30。

>哈希查找

1.哈希函數的構造方法

哈希查找(HashSearch)算法是通過計算數據元素的存儲地址來進行

查找的一種算法。算法的原理是查找時通過給定值k以及對應關系f,便

可以找到k值所對應的哈希地址f(k)(不需要比較直接獲得查找目標)。

這種對應關系f就是哈希函數，通過這個思想建立的表稱為哈希表。

哈希函數的構造方法有很多，具體如下。

(1)直接定址法。取關鍵字或關鍵字的某個線性函數值作為哈希地址,

即H(key)=key或H(key)=aXkey+b(a,b為常數)。

(2)數字分析法。取關鍵字中某些取值較均勻的數字位作為哈希地址。

當關鍵字的位數很多時，可以通過對關鍵字的各位進行分析，去掉分布不均

勻的位。這種方法只適合于所有關鍵字已知的情況。通過分析分布情況將關

鍵字取值區(qū)間轉化為一個較小的關鍵字取值區(qū)間。

(3)平方取中法。取關鍵字平方后的中間幾位作為哈希地址。

(4)折疊法。將關鍵字分割成位數相同的幾個部分(最后一部分的位數

可以不同)，然后取這幾部分的疊加和(舍去進位)作為哈希地址。這種方

法適用于關鍵字位數比較多，且關鍵字中每一位上數字分布大致均勻的情

況。

(5)除留余數法。取關鍵字被某個不大于哈希表表長m的數p除后

所得的余數作為哈希地址(P為素數)。

(6)隨機數法。選擇一個隨機函數，取關鍵字的隨機函數值作為其哈希

地址，即H(key)=random(key),其中random。為隨機函數。該方法適用于

關鍵字長度不等的情況。

2.哈希沖突

由于通過哈希函數產生的哈希地址是有限的，而在數據比較多的情況

下，經過哈希函數處理后，不同的數據可能會產生相同的哈希地址，這就造

成了哈希沖突，如圖所示。

關鍵字

>排序的概念

排序指的是將無序的記錄按照其中某個(或某些)關鍵字的大小以遞增

或遞減的順序排列起來的操作。其確切的定義為：假設有n個數據元素的

序列(R1,R2，…Rn),其相應關鍵字的序列是(K1,K2,-Kn),要

求通過排序找出下標1,2,-n的一種排列P1,P2,…Pn,使得相應關

鍵字滿足非遞減(或非遞增)關系KplWKp2W…<Kpn,從而得到一

個按關鍵字有序排列的記錄序列(Rpl,Rp2…Rpn)?

按照排序過程中涉及的存儲器的不同，可以將排序分為內部排序與外部

排序。內部排序指的是待排序的記錄數較少，所有的記錄都能存放在內存中

進行排序。外部排序指的是待排序的記錄數太多，不可能把所有的記錄存放

在內存中，排序過程中必須在內存與外存之間進行數據交換。

＞直接插入排序

1.直接插入排序概述

直接插入排序(InsertionSort)是一種簡單直觀的排序算法，其工作

原理是先構建有序序列，然后在已排序序列中從后向前掃描，為未排序的數

據找到相應位置并將其插入。

直接插入排序算法的具體操作步驟如下所示。

(1)從序列的第一個元素開始，該元素被認定為已排序。

(2)在已排序的元素序列中從后向前掃描，為下一個元素尋找位置。

(3)如果已排序的元素大于新插入的元素，則將已排序元素移動到下

一位。

(4)重復步驟(3),直到已排序元素小于或等于新插入的元素。

(5)插入新元素。

(6)重復步驟(2)?(5)。

2.直接插入排序代碼實現

直接插入排序的代碼參考教材6.2.2節(jié)。

＞希爾排序

1.希爾排序概述

希爾排序(ShellSort)是希爾(DonaldShell)于1959年提出的

一種排序算法。希爾排序同樣是一種插入排序，它是直接插入排序經過改進

之后的一個更高效的版本，也稱為縮小增量排序。希爾排序與直接插入排序

的不同之處在于，希爾排序會優(yōu)先比較距離較遠的元素。

希爾排序的核心操作是將序列按照增量(增量等于組的數量)進行分組,

然后對每一組中的序列使用直接插入排序算法進行排序。當所有組中的序列

都完成排序后，增量變小，按照減小的增量再次分組(分組不影響元素的位

置)，分組后再進行直接插入排序，以此類推(增量越小，每組的元素就越

多)。當增量減小為1時，整個序列分為一組，算法結束。

希爾排序在選擇增量時，可以使增量gap=length/2(length為序列長

度)，縮小增量可以使用gap=gap/2的方式，這種增量可以用一個序列來表

示，稱為增量序列。

2.希爾排序代碼實現

希爾排序算法的代碼參考教材6.2.3節(jié)。

第二課時

(排序)

Q內容回顧

i.回顧上節(jié)內容，引出本課時主題。

上節(jié)已經介紹了順序查找、折半查找、分塊查找、哈希查找、排序的概

念、直接插入排序和希爾排序，下面將介紹直接選擇排序、堆排序、冒泡排

序、快速排序和歸并排序。

2.明確學習目標

(1)能夠掌握直接選擇排序

(2)能夠掌握堆排序

(3)能夠掌握冒泡排序

(4)能夠掌握快速排序

(5)能夠掌握歸并排序

Q知識講解

＞直接選擇排序

i.直接選擇排序概述

直接選擇排序(SelectionSort)是比較穩(wěn)定的排序算法，其時間復雜度

在任何情況下都是0(n2)。

直接選擇排序是一種簡單直觀的排序算法，排序過程中，無須占用額外

的空間。直接選擇排序的工作原理是：首先在未排序的序列中找到最小(大)

元素，存放到已排序序列的末尾；然后從剩余未排序元素中尋找最小(大)

元素，放到已排序序列的末尾；以此類推，直到所有元素排序完畢。

由上述描述可知，直接選擇排序就是反復從未排序的序列中取出最小

(大)的元素，加入另一個序列，最后得到已經排好的序列。接下來通過具

體的序列對直接選擇排序算法進行說明。如圖所示，創(chuàng)建一個原始的未排序

的序列。

未排序@(7)(4)000

2.直接選擇排序代碼實現

直接選擇排序的代碼參考教材6.2.4節(jié)。

＞堆排序

1.堆排序概述

堆排序(HeapSort)是利用數據結構堆設計的一種排序算法。堆是一個

近似完全二叉樹的結構。如果堆中每個結點的值都大于或等于其左右孩子的

值，則該堆稱為大頂堆：如果堆中每個結點的值都小于或等于其左右孩子的

值，則該堆稱為小頂堆，如圖所示。

2

?'t°2F

3(18)(15)43(12).4

大頂堆小頂堆

2.堆排序代碼實現

堆排序的代碼參考教材6.2.5節(jié)。

>冒泡排序

1.冒泡排序概述

冒泡排序(BubbleSort)是一種簡單且經典的排序算法。冒泡排序的核

心思想是重復遍歷整個序列，從第一個元素開始，兩兩比較相鄰元素的大小,

如果反序則交換，直到整個序列變?yōu)橛行驗橹埂?/p>

冒泡排序算法的具體操作步驟如下所示。

(1)比較相鄰元素，從第一個元素開始，即第一個元素與第二個元素比

較，如果前一個元素大于后一個元素就進行交換。

(2)每次比較完成后，移動到下一個元素繼續(xù)進行比較，直到比較完最

后一個元素與倒數第二個元素。

(3)所有元素比較完成后(一輪比較)，序列中最大的元素在序列的末

尾。

(4)重復上述3個步驟。

2.冒泡排序代碼實現

冒泡排序的代碼參考教材6.2.6節(jié)。

>快速排序

快速排序(QuickSort)的核心思想是通過一輪排序將未排序的序列分為

獨立的兩部分，使得一部分序列的值比另一部分序列的值小，然后分別對這

兩部分序列繼續(xù)進行排序，以達到整個序列有序。

快速排序使用分治法將一個序列分為兩個子序列，其具體的算法描述如

下。

(1)從序列中選出一個元素，作為基準值。

(2)重新排序，將所有比基準值小的元素放到基準值前，所有比基準值

大的元素放到基準值后(與基準值相同的元素可以到任一邊)。

(3)采用遞歸的思想對小于基準值的子序列和大于基準值的子序列排

序。

在上述算法描述的基礎上，快速排序可以設計出很多版本。接下來將通

過具體的序列展示快速排序的兩個版本，分別為單指針遍歷法與雙指針遍歷

法(指針指的是方向選擇，不是語法意義上的指針)。

1.單指針遍歷法

如圖所示，創(chuàng)建一個無序的數字序列。

未排序序列

57164832

2.單指針遍歷法實現快速排序

采用單指針遍歷法實現快速排序代碼參考教材6.2.7節(jié)。

3.雙指針遍歷法

在單指針遍歷法中，每次都是選擇一個元素與基準值進行比較，而雙指

針遍歷法是同時選擇兩個元素與基準值進行比較。如圖所示，創(chuàng)建一個無序

序列。

未排序序列

1517101614181312

ij

4.雙指針遍歷法實現快速排序

采用雙指針遍歷法實現快速排序，示例代碼參考教材6.2.7節(jié)。

>歸并排序

1.歸并排序概述

歸并排序(MergingSort)是利用歸并的思想設計的一種排序算法，該算

法是采用分治法的一個非常典型的應用。歸并排序是一種穩(wěn)定