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

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

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

2.折半查找

又稱為二分查找，用于待查數(shù)據(jù)元素序列是采用順序存儲結(jié)構(gòu)的有序表情況。1）基本思想假設(shè)待查序列按照數(shù)據(jù)元素的值升序排列，在查找時不必順序進(jìn)行比較，而是將待查關(guān)鍵字key先與“中間位置”數(shù)據(jù)元素的值比較，若相等，則查找成功。若key小于“中間位置”的數(shù)據(jù)元素值，則在有序表的前半部按上述方法進(jìn)行查找；否則，在有序表的后半部按上述方法查找。2）算法流程與實現(xiàn)#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])/*繼續(xù)在前半?yún)^(qū)間范圍查找*/hig=mid-1; elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間范圍查找*/}return0;}例10-1

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

折半查找判定樹中每個結(jié)點對應(yīng)待查找序列的一個數(shù)據(jù)元素，結(jié)點值是該數(shù)據(jù)的下標(biāo)序號，根結(jié)點是待查序列中間數(shù)據(jù)的下標(biāo)位置序號mid，左子樹為mid位置左邊結(jié)點的下標(biāo)位置序號，右子樹為mid位置右邊結(jié)點的下標(biāo)位置序號。圈外數(shù)字是數(shù)據(jù)元素值;圈內(nèi)數(shù)字是對應(yīng)下標(biāo)位置序號。待查找結(jié)點在判定樹中的層數(shù)為折半查找成功的比較次數(shù)。

例10-2

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

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

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

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

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

2.冒泡排序

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

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

05排序方法應(yīng)用舉例例10-8

青年歌手大賽，有10位評委進(jìn)行打分，每位選手的最后得分為：去掉1個最高分和1個最低分后，8位評委的總分。要求編寫一個通用程序，輸入各選手的編號、各位評委的評分，輸出各選手的編號、總分及名次。采用模塊化思想，可設(shè)置4個函數(shù)如下：①sum1函數(shù)。計算各選手總分。②sort1函數(shù)。應(yīng)用冒泡排序方法，總分由高到低排序。③print1函數(shù)。輸出各選手的編號、總分和名次。④main主函數(shù)。輸入各選手的編號、各位評委的評分，分別調(diào)用以上3個函數(shù)。定義標(biāo)識符說明：M：符號常量，設(shè)有10位評委。N：符號常量，設(shè)有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]; /*設(shè)置初值*/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