常用的查找和排序方法《計算機軟件基礎》01.查找的概念02.常用的靜態查找03.排序的概念主要內容05.排序方法應用舉例04.常用的內部排序本章重點難點本章重點：三種查找和三種排序方法的基本思想和操作過程。本章難點：三種查找和三種排序方法的算法實現。查找和排序是數據處理過程的主要操作查找即在一個含有眾多的數據元素（記錄）集合中找出某個特定的數據元素。排序就是把一組數據元素（記錄）按其關鍵字的某種次序排列起來，使其具有一定順序，便于查找。查找和排序的方法很多，針對不同的數據結構，需要采用不同的查找和排序方法。01查找的概念1.查找的概念查找表是由同一類型的數據元素構成的集合。查找就是根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。若查找表中存在這樣一個記錄，則為“查找成功”，其查找結果為：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則為“查找失敗”，其查找結果為空。對查找表進行的操作有以下四種:010203查詢某個特定的數據元素是否在查找表中04檢索某個特定的數據元素的各種屬性在查找表中插入一個數據元素從查找表中刪除某個數據元素靜態查找表：若對查找表只做前兩種操作，即只執行查找操作。動態查找表：若在查找過程中同時插入查找表中不存在的數據元素，或者從查找表中刪除已存在的某個數據元素。

02常用的靜態查找1.設“監視哨”的順序查找順序查找是一種最基本、直接的查找方法。它從線性表的一端開始，向另一端逐個取出數據元素的關鍵字，并與要查找的關鍵字key進行比較，以判斷是否存在要找的關鍵字。1）基本思想假設n個數據元素已存入一維數組a[1..n]的區域中，a[0]作為監視哨，存放要查找的關鍵字key。順序查找的整個過程是從最后一個數據元素a[n]開始，向前依次與key比較，直至a[1]，若數據元素的值和key都不相等時，則返回0，查找失敗；否則返回數據元素的下標位置，查找成功。2）算法流程與實現設低位監視哨的順序查找流程#include<stdio.h>intsearch_seq(inta[],intkey,intn){inti=n;a[0]=key;

/*設“監視哨”*/while(a[i]!=key)/*從第n個元素到第1個依次找key*/i--;returni;}3）平均查找長度

2.折半查找

又稱為二分查找，用于待查數據元素序列是采用順序存儲結構的有序表情況。1）基本思想假設待查序列按照數據元素的值升序排列，在查找時不必順序進行比較，而是將待查關鍵字key先與“中間位置”數據元素的值比較，若相等，則查找成功。若key小于“中間位置”的數據元素值，則在有序表的前半部按上述方法進行查找；否則，在有序表的后半部按上述方法查找。2）算法流程與實現#include<stdio.h>intsearch_bin(inta[],intkey,intn){intlow,mid,hig;low=1;hig=n;while(low<=hig){ mid=(low+hig)/2;if(key==a[mid])returnmid;/*找到則返回位置序號*/elseif(key<a[mid])/*繼續在前半區間范圍查找*/hig=mid-1; elselow=mid+1;/*繼續在后半區間范圍查找*/}return0;}例10-1

已知待查序列為：2，5，9，13，18，26，32。待查關鍵字K分別為13、32和4，試寫出折半查找過程。3)折半查找判定樹

折半查找判定樹中每個結點對應待查找序列的一個數據元素，結點值是該數據的下標序號，根結點是待查序列中間數據的下標位置序號mid，左子樹為mid位置左邊結點的下標位置序號，右子樹為mid位置右邊結點的下標位置序號。圈外數字是數據元素值;圈內數字是對應下標位置序號。待查找結點在判定樹中的層數為折半查找成功的比較次數。

例10-2

試構造具有9個結點的折半查找判定樹，并求查找成功的平均查找長度ASL。樹的特點？？

3.二叉查找樹查找1）二叉查找樹定義一棵二叉查找樹（又稱二叉搜索樹）是一棵二叉樹，它可以為空。如果不為空，它將滿足下列條件：根的非空左子樹的所有結點的關鍵字小于根結點的關鍵字。根的非空右子樹的所有結點的關鍵字大于根結點的關鍵字。左、右子樹都是二叉查找樹。2）二叉查找樹上的查找由于二叉查找樹的特殊性質，查找可以比較方便地實現。其過程如下：1）查找從樹的根結點開始，如果樹為空，返回NULL，表示未找到關鍵字為key的結點。2）查找樹非空，則根結點關鍵字和key進行比較，依據比較結果，需要進行不同的處理：若根結點關鍵字小于key，則在此根結點的右子樹中繼續進行查找；若根結點關鍵字大于key，則在此根結點的左子樹中繼續進行查找；若兩者比較結果是相等，查找完成，返回指向此結點的指針。3）構造二叉查找樹的方法已知一個關鍵字序列，構造二叉查找樹的方法通常是通過逐個插入序列中的關鍵字來完成的。以下是一種常見的方法：創建一個空的二叉查找樹。從序列中取出第一個關鍵字作為根結點，將其插入到二叉查找樹中。對于序列中的每個后續關鍵字，按照以下規則進行插入：從根結點開始，遞歸地比較要插入關鍵字和當前結點關鍵字。如果要插入關鍵字小于當前結點的關鍵字，則向其左子樹移動；如果該大于當前結點的關鍵字，則向其右子樹移動。重復步驟③直到遇到一個空的子結點（即空指針），表示找到了插入位置，將要插入關鍵字作為新結點插入到這個空的子結點位置。重復步驟③和④，直到遍歷完整個序列，插入所有關鍵字為止。已知關鍵字序列為37、21、30、50、35、40、12，其二叉查找樹的構造過程如下圖4）二叉查找樹上結點的平均查找長度二叉查找樹和折半查找判定樹類似，各結點的成功查找長度就是結點所在層數。因此，二叉查找樹的平均查找長度不僅與結點個數n有關，而且與樹形有關。同一組數，插入順序不同，構造的樹形不同，其查找成功的平均查找長度也不一定相同。例如，由2、4、6、8、10和6、10、2、8、4所構造的二叉查找樹如圖a)、b)所示。b)查找成功的平均查找長度？？？

03排序的概念內部排序：是指待排序數據元素存放在計算機隨機存儲器中進行的排序過程。外部排序：指待排序數據元素的數量較大，內存一次不能容納全部數據元素，在排序過程中尚需對外存進行訪問的排序過程

衡量一個排序算法，通常使用以下三個性能指標：1）時間復雜度。時間復雜度主要取決于關鍵字的比較次數和數據元素的移動次數。2）空間復雜度。排序算法所需要的輔助空間取決于所用的算法本身。3）穩定性。

排序算法的穩定性是指在待排序的一組數據中，若有兩個相同的關鍵字在排序前和排序后，它們的先后順序沒有發生變化，則稱這種排序算法是穩定的，否則是不穩定的。04常用的內部排序根據排序方法進行一趟的基本操作不同，內部排序方法分為下面幾大類：基于“插入”思想的排序方法執行一趟是將一個元素“插入”到有序序列中仍然有序，使有序部分擴大。這類方法有：直接插入排序折半插入排序2路插入排序SHELL排序基于“交換”思想的排序方法執行一趟是通過交換“逆序”元素使之到有序序列中，使有序部分擴大。這類方法有：冒泡（標準交換）排序奇偶（成對）交換排序穿梭排序快速排序基于“選擇”思想的排序方法執行一趟是通過出當前無序部分的最小元素放到有序序列的后面，使有序部分擴大。這類方法有：簡單選擇排序錦標賽（打擂臺）排序堆排序其他思想的排序方法基數排序計數排序基于“歸并”思想的排序方法執行一趟是通過歸并兩個短的有序序列為一個有序序列，使有序部分擴大。這類方法有：2路歸并排序多路歸并排序1.直接插入排序其基本思想是將待排序線性表分為有序序列和無序序列兩部分，將無序序列的一個或幾個數據元素插入到有序序列的合適位置，直到全部數據元素有序為止。

2.冒泡排序

基本思想是對所有相鄰元素的關鍵字進行比較，如果是逆序，則將其交換，最終達到有序。冒泡排序方法簡單，應用廣泛。例10-6將9，5，2和4這4個數據元素用冒泡排序的方法進行排序。先把4個數依次存入x[1..4]數組中，具體排序過程如圖所示。

3.直接選擇排序直接選擇排序的基本思想是將未排好序的序列中最小元素依次添加到已排好序的序列的一端。將5、8、2、4、6、1用直接選擇排序方法排序，方法如圖所示，圓圈內數字為已排好序的數。

05排序方法應用舉例例10-8

青年歌手大賽，有10位評委進行打分，每位選手的最后得分為：去掉1個最高分和1個最低分后，8位評委的總分。要求編寫一個通用程序，輸入各選手的編號、各位評委的評分，輸出各選手的編號、總分及名次。采用模塊化思想，可設置4個函數如下：①sum1函數。計算各選手總分。②sort1函數。應用冒泡排序方法，總分由高到低排序。③print1函數。輸出各選手的編號、總分和名次。④main主函數。輸入各選手的編號、各位評委的評分，分別調用以上3個函數。定義標識符說明：M：符號常量，設有10位評委。N：符號常量，設有5位選手。a[1..M]：10位評委的打分。b[1..N]：5位選手最后得分。c[1..N]：選手的編號。intsum1(intx[],intn) /*計算各位選手總分*/{inti,max,min,s; /*max和min分別記錄最高分和最低分，s記錄評分和*/max=min=s=x[1]; /*設置初值*/for(i=2;i<=n;i++){if(x[i]>max)max=x[i]; /*求最高分*/if(x[i]<min)min=x[i]; /*求最低分*/s=s+x[i]; /*評委總分*/}s=s-max-min; /*去掉1個最高分和1個最低分后選手的最后得分*/returns;}v