計(jì)算機(jī)軟件基礎(chǔ)課件：查找與排序

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

02常用的靜態(tài)查找1.設(shè)“監(jiān)視哨”的順序查找順序查找是一種最基本、直接的查找方法。它從線性表的一端開(kāi)始，向另一端逐個(gè)取出數(shù)據(jù)元素的關(guān)鍵字，并與要查找的關(guān)鍵字key進(jìn)行比較，以判斷是否存在要找的關(guān)鍵字。1）基本思想假設(shè)n個(gè)數(shù)據(jù)元素已存入一維數(shù)組a[1..n]的區(qū)域中，a[0]作為監(jiān)視哨，存放要查找的關(guān)鍵字key。順序查找的整個(gè)過(guò)程是從最后一個(gè)數(shù)據(jù)元素a[n]開(kāi)始，向前依次與key比較，直至a[1]，若數(shù)據(jù)元素的值和key都不相等時(shí)，則返回0，查找失??；否則返回?cái)?shù)據(jù)元素的下標(biāo)位置，查找成功。2）算法流程與實(shí)現(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個(gè)元素到第1個(gè)依次找key*/i--;returni;}3）平均查找長(zhǎng)度

2.折半查找

又稱(chēng)為二分查找，用于待查數(shù)據(jù)元素序列是采用順序存儲(chǔ)結(jié)構(gòu)的有序表情況。1）基本思想假設(shè)待查序列按照數(shù)據(jù)元素的值升序排列，在查找時(shí)不必順序進(jìn)行比較，而是將待查關(guān)鍵字key先與“中間位置”數(shù)據(jù)元素的值比較，若相等，則查找成功。若key小于“中間位置”的數(shù)據(jù)元素值，則在有序表的前半部按上述方法進(jìn)行查找；否則，在有序表的后半部按上述方法查找。2）算法流程與實(shí)現(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;/*找到則返回位置序號(hào)*/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，試寫(xiě)出折半查找過(guò)程。3)折半查找判定樹(shù)

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

例10-2

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

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

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

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

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

2.冒泡排序

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

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

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

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