第6章算法與數(shù)據結構大學計算機基礎課程組2022年4月程序數(shù)據結構=算法+主要內容算法的基本知識1數(shù)據結構基礎2幾種常見的算法33主要內容1算法及其基本特點算法描述方法算法復雜度分析數(shù)據結構基礎2幾種常見的算法34算法的基本知識數(shù)據結構的概念常見的幾種數(shù)據結構及其基本操查找算法、排序算法、遞推算法、枚舉算法、貪心算法、分治算法算法(algorithms):是為了求解問題而給出的有限的指令序列，每條指令表示一個或多個操作。——解決問題的步驟程序是算法的一種實現(xiàn)，計算機按照程序逐步執(zhí)行算法，實現(xiàn)對問題的求解。6.1算法（algorithm）基礎方案設計方案實現(xiàn)數(shù)據模型基本想法數(shù)據表示數(shù)據處理選擇語言選擇IDE方法設計6.1.1計算機求解問題的過程6.1.2算法的特點有窮性：一個算法必須能在執(zhí)行有窮步之后結束，且每一步都可在有窮時間內完成；確定性：算法中每一條指令必須有確切的含義，不具有二義性。可行性：算法中描述的操作都可通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。輸入：一個算法有零個或多個輸入，這些輸入取自某個特定的對象的集合輸出：一個算法有一個或多個輸出，這些輸出是同輸入具有某種特定關系的量。算法設計者在構思和設計了一個算法之后，必須清楚準確地將所設計的求解步驟記錄下來，即描述算法。常用的描述算法的方法有自然語言流程圖程序設計語言偽代碼等。下面以計算10個數(shù)的平均值算法為例進行介紹6.1.3算法的描述方法自然語言（1）定義一個變量sum用來記錄10個數(shù)的和，并給其賦值為0。（2）輸入一個數(shù)x，并將輸入的這個數(shù)x與sum進行加法計算，用sum記錄加法計算的結果。（3）重復執(zhí)行（2）10次。第1次執(zhí)行（2）時sum中記錄了第1個數(shù)的值，第2次執(zhí)行（2）后sum中記錄了前2個數(shù)的和，第3次執(zhí)行（2）后sum中記錄了前3個數(shù)的和……，第10次執(zhí)行（2）后sum中記錄下了10個數(shù)的和。（4）將sum除以10，得到10個數(shù)的平均值。用自然語言描述算法，最大的優(yōu)點是容易理解，缺點是容易出現(xiàn)二義性，并且算法通常都很冗長流程圖用流程圖描述算法，優(yōu)點是直觀易懂，缺點是嚴密性不如程序設計語言，靈活性不如自然語言程序設計語言用程序設計語言描述的算法能由計算機直接執(zhí)行，而缺點是抽象性差.#include<stdio.h>intmain(){floatsum=0,x; inti=1; while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}偽代碼偽代碼是介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。（1）sum=0,i=1;（2）如果i<=10,則執(zhí)行下面操作，否則，轉（3）。

①輸入x;

②sum=sum+x;

③i=i+1;

④轉（2），繼續(xù)執(zhí)行（3）輸出sum/10.6.1.4算法復雜度分析解決同一個問題總是存在著多種算法，而算法設計者在所花費的時間和所使用的空間資源往往要兩者之間采取折中。算法設計者可以通過算法分析，判斷所提出的算法是否現(xiàn)實，分析算法的效率以求改進。算法分析的內容算法運行所需要的時間，稱為時間復雜性算法運行所需要的輔助空間，稱為空間復雜性撇開與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模n，即輸入量的大小。如： 對一個長度是n一維數(shù)組排序，問題規(guī)模為n

對一個m*n的二維數(shù)組進行排序，問題規(guī)模為m*n算法執(zhí)行時間T是問題規(guī)模的函數(shù)，計為T(n).

算法時間復雜度分析算法的時間復雜度估計主要評估n逐步增大時，T(n)的增長趨勢#include<stdio.h>intmain(){

floatsum=0,x; inti=1,n;

scanf("%d”,&n);while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}

n程序的執(zhí)行時間:∑語句i的執(zhí)行次數(shù)×執(zhí)行時間

i=1(=1)語句頻度:語句重復執(zhí)行的次數(shù)計算機執(zhí)行簡單操作的時間，可認為是常量。nnnn11時間復雜度：

算法的執(zhí)行時間(所有語句的語句頻度之和）T(n)=1+n+n+n+n+1=2+4n問題規(guī)模：求解問題的輸入量

limT(n)/n=lim(2+4n)/n=1n－>∞當問題規(guī)模n→∞時T(n)與某一量同階,稱作算法的漸近時間復雜度（asymptotictimecomplexity，隨著問題規(guī)模的增加，算法運行時間的增長趨勢）

：記作：T(n)=O(n)O是order的簡寫例2:算法的時間復雜度分析intcount=0;

O(1)O(n)count=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)count++;O(n2)intn=8,count=0,i;for(i=1;i<=n;i++)count++;常見的時間復雜度量級有常數(shù)階O(1)（算法執(zhí)行時間是一個與問題規(guī)模無關的常數(shù)）、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、K次方階O(nk)、指數(shù)階O(2n)等等。算法的空間復雜度算法的空間復雜度是指在算法的執(zhí)行過程中，需要的輔助空間數(shù)量。輔助空間是除算法本身和輸入輸出數(shù)據所占據的空間外，算法臨時開辟的存儲空間。通常記作：S(n)=O(f(n))其中，n為問題規(guī)模，分析方法與算法的時間復雜度類似。輔助空間的統(tǒng)計將數(shù)組a中的元素逆置方法一：intx;for(i=0;i<n/2;i++) x=a[i];a[i]=a[n-i];a[n-i]=x;方法二：intb[]for(i=0;i<n;i++)b[i]=a[n-i];for(i=0;i<n;i++)a[i]=b[i];需要一個輔助空間，O(1)需要年n個輔助空間，O(n)6.2數(shù)據結構基礎用計算機求解問題一般包含兩個步驟：⑴抽象出問題的模型；⑵求該模型的解。對于數(shù)值問題抽象出的模型通常是數(shù)學方程，例如圖形的面積與周長等預報人口增長情況的模型更多的非數(shù)值問題是難以用數(shù)學方程來描述的。數(shù)值計算問題實例：計算課程平均成績學號姓名班級性別課程成績2021001韓華計算機21-1女832021002劉明計算機21-1男802021003劉茜計算機21-1女902021004王藝計算機21-1男75大學計算機課程成績表要完成平均成績的計算，需要將所有同學的考試成績加起來，然后除以學生總人數(shù)，即可得到該門課程的平成績。該問題屬于數(shù)值計算問題非數(shù)值計算問題實例：確定學生名次學號姓名班級性別課程成績2021001韓華計算機21-1女832021002劉明計算機21-1男802021003劉茜計算機21-1女902021004王藝計算機21-1男75大學計算機課程成績表要排出名次，需要按照考試成績對表中數(shù)據進行降序排序。該操作不會修改表中數(shù)據的值，只會改變表中數(shù)據的排列順序。這類問題不能通過設計一個數(shù)學模型的方式來解決，屬于非數(shù)值計算問題非數(shù)值計算問題實例：微信聯(lián)系人管理6.2.2數(shù)據結構的幾個基本概念數(shù)據（Data）:是對客觀事物的符號表示，在計算機科學中是指能輸入到計算機并被計算機程序處理的符號的總稱。數(shù)據元素（DataElement）:是數(shù)據的基本單位，也可以稱為結點，在計算機程序中通常作為一個整體進行考慮。數(shù)據項（DataItem）：數(shù)據元素一般由若干數(shù)據項組成，數(shù)據項是構成數(shù)據元素最小的、不可分割的單位。數(shù)據結構（DataStructure）:

相互之間存在一定關系的數(shù)據的集合。 是數(shù)據及其元素之間相互關系的表示。邏輯結構：數(shù)據元素之間一般存在某種特定的關系，這種關系稱為數(shù)據的邏輯結構。物理結構（存儲結構）：數(shù)據結構在計算機內存中的表示形式。包括數(shù)據元素的表示和其關系的表示。邏輯結構線性結構（linearstructure）樹型結構（treestructure）圖結構（graphstructure）集合（set）線性結構實例學號姓名班級性別課程成績2021001韓華計算機21-1女832021002劉明計算機21-1男802021003劉茜計算機21-1女902021004王藝計算機21-1男75線性關系具有以下特點：（1）有且僅有一個開始結點和一個終端結點（注：一個結點即為一個數(shù)據元素）。（2）其余所有結點都只有一個直接前驅和一個直接后繼。樹結構：樹結構具有以下特點：（1）只有一個結點沒有直接前驅。（2）可以有多個結點沒有直接后繼。（3）樹中的每個結點，如果有直接前驅，直接前驅只有一個；如果有直接后繼，直接后繼可以有多個。圖結構在圖結構中一個結點可以有0個或多個直接前驅和直接后繼。ABDCAEDCBDACBE樹狀結構圖或網狀結構CBDA集合線性結構數(shù)據的存儲結構計算機的主存儲器的特性其存儲空間提供了一種具有非負整數(shù)地址編碼的，相鄰單元的集合，其基本的存儲單元是字節(jié)計算機的指令具有按地址隨機訪問存儲空間內任意單元的能力，訪問不同地址所需的訪問時間基本相同數(shù)據的存儲結構又稱物理結構，是數(shù)據及其邏輯結構在計算機中的表示存儲結構的分類：1.順序結構 2.鏈式結構順序（sequential）存儲用一塊無空隙的存儲區(qū)域存儲數(shù)據稱為順序存儲順序存儲把一組結點存儲在按地址相鄰的順序存儲單元里，結點間的邏輯后繼關系用存儲單元的自然順序關系來表達鏈式（linked）存儲ABCF

DE6.2.5幾種常見的數(shù)據結構線性表棧隊列二叉樹線性表及其基本操作由0個或多個具有線性邏輯關系的數(shù)據元素組成的一個有限序列稱為線性表(LinearList)。可以采用下面的通用形式描述一個線表：L=（a1,a2,a3,……,an）在上述形式化的描述中,ai代表一個數(shù)據元素，下標i代表數(shù)據元素在線性表中的編號。可以采用順序存儲結構或鏈式存儲結構存儲一個線性表順序表采用順序存儲結構存儲的線性表稱為順序表。順序存儲是利用一維數(shù)組實現(xiàn)的。順序表中查找第i個數(shù)據元素根據順序存儲的特點，可以直接利用順序表中第一個數(shù)據元素的地址（用loc(a1)表示），計算出順序表中第i個數(shù)據元素的地址（用loc(ai)表示）,計算公式見公式（1）：loc(ai)=loc(a1)+(i-1)*c （公式1）公式（1）中的c是一個整數(shù)，表示每個數(shù)據元素所占內存大小。算法的時間復雜度為O(1)。順序表中插入第i個數(shù)據元素插入操作是指在長度為n的順序表中插入一個數(shù)據元素，插入之后順序表的長度變?yōu)閚+1。時間復雜度為O(n)順序表中刪除第i個數(shù)據元素刪除操作是指在長度是n的順序表中刪除一個數(shù)據元素，刪除之后順序表的長度變?yōu)閚-1。刪除操作可以按位置刪除，也可以按值刪除。按位置刪除時，需要指明刪除的位置；按值刪除時，需要查找要刪除的元素在順序表中的位置，之后再進行刪除。時間復雜度為O(n)單鏈表及基本操作單鏈表中查找第i個數(shù)據元素利用工作指針移動的次數(shù)評估算法的時間復雜度。分析這一查找過程可以看到，查找操作所需要移動指針的次數(shù)與單鏈表的長度成正比該查找算法的時間復雜度為度為O(n)單鏈表中插入第i個數(shù)據元素單鏈中第5個元素的位置上插入88時間復雜度也為O(n)單鏈表中刪除第i個數(shù)據元素單鏈中刪除第5個元素的操作過程。時間復雜度也為O(n)雙鏈表可以采用雙鏈表存儲一個線性表。在雙鏈表中，每個結點既存儲了后繼結點的地址，又存儲了其前驅結點的地址。雙鏈表中插入第i個數(shù)據元素時間復雜度為O(n)雙鏈表中刪除第i個數(shù)據元素時間復雜度為O(n)棧是僅允許在線性表的同一端進行插入或刪除操作的線性表允許插入或刪除操作的這一端稱為棧頂,另一端稱為棧底棧具有FILO（FirstInLastOut）的特點。a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖棧的操作特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧的示意圖例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？情況1：棧底棧頂ab棧頂出棧序列：b情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？情況2：隊列空隊列：不含任何數(shù)據元素的隊列。

隊列：只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。（a1,a2,……,an）隊尾隊頭a1a2a3入隊隊尾隊頭出隊隊頭隊列的操作特性：先進先出(FIFO,LILO)二叉樹二叉樹中包含n(n>=0)個結點。n為0時，二叉樹是一棵空樹。非空的二叉樹中包含一個樹根；除根結點外，其余的結點分為兩個互不相交的子集，分別稱為根結點的左子樹和右子樹。二叉樹的基本形態(tài)Ф空二叉樹只有一個根結點左子樹根結點只有左子樹右子樹根結點只有右子樹左子樹右子樹根結點同時有左右子樹結點的度：結點所擁有的子樹的個數(shù)。葉子結點：度為0的結點，也稱為終端結點。分支結點：度不為0的結點，也稱為非終端結點。孩子、雙親：樹中某結點子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；兄弟：具有同一個雙親的孩子結點互稱為兄弟。結點所在層數(shù)：根結點的層數(shù)為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。樹的深度：樹中所有結點的最大層數(shù)，也稱高度。層序編號：將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。特殊的二叉樹斜樹1.所有結點都只有左子樹的二叉樹稱為左斜樹；2.所有結點都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個結點；2.斜樹的結點個數(shù)與其深度相同。

斜樹的特點：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結點。特殊的二叉樹CDEFGHIJKLMNO1112131415滿二叉樹不是滿二叉樹，雖然所有分支結點都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結點個數(shù)最多A1523467BCDEFGLM89特殊的二叉樹完全二叉樹對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1≤i≤n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同。特殊的二叉樹CDEFGHIJKLMNO1112131415CDEFGHIJ在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結點10與滿二叉樹中的結點10不是同一個結點特殊的二叉樹1.葉子結點只能出現(xiàn)在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點CDEFGHIJ性質1：二叉樹的第k層最多有2k-1個結點。性質2：深度為k的二叉樹中最多有2k-1個結點；最少有k個結點。性質3：在一棵二叉樹中，度為0的結點個數(shù)比度為2的結點個數(shù)多一個。性質4：含有n個結點的完全二叉樹的高度為log2n。性質5：完全二叉樹中編號是i的結點，如果有左兒，左兒子的編號是2×i，如果有右兒子，右兒子的編號是2×i+1；如果有父親，父親編號是i/2。【性質1】在二叉樹的第k層上最多有2k-1個結點（k≥1）ABCDFEHG【性質2】深度為m的二叉樹最多有2m-1個結點（m≥1）A1523467910BCDEFGHIJK11L12M13N14O158【性質3】在任意一棵二叉樹中，若度為0的結點（即葉子結點）的個數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1。

ABCDFEHG度為2的結點葉子結點性質3：在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0＝n2＋1。

證明:設n為二叉樹的結點總數(shù)，n1為二叉樹中度為1的結點數(shù)，則有：

n＝n0＋n1＋n2

在二叉樹中，除了根結點外，其余結點都有唯一的一個分枝進入，由于這些分枝是由度為1和度為2的結點射出的，一個度為1的結點射出一個分枝，一個度為2的結點射出兩個分枝，所以有：

n＝n1＋2n2＋1因此可以得到：n0＝n2＋1。在有n個結點的滿二叉樹中，有多少個葉子結點？因為在滿二叉樹中沒有度為1的結點，只有度為0的葉子結點和度為2的分支結點，所以，n＝n0+n2n0＝n2+1

即葉子結點n0＝（n+1）/2

性質3：在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0＝n2＋1。

性質4：具有n個結點的完全二叉樹的深度為log2n+1。

證明：假設具有n個結點的完全二叉樹的深度為k，根據完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結點數(shù)最多結點數(shù)

證明：假設具有n個結點的完全二叉樹的深度為k，根據完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k性質4：具有n個結點的完全二叉樹的深度為log2n+1。

對不等式取對數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。

性質5：對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結點（簡稱為結點i），有：

（1）如果i＞1， 則結點i的雙親結點的序號為

i/2；如果i＝1， 則結點i是根結點，無雙親結點。(2)如果2i≤n， 則結點i的左孩子的序號為2i； 如果2i＞n，則結點i無左孩子。(3)如果2i＋1≤n， 則結點i的右孩子的序號為2i＋1；如果2i＋1＞n，則結點

i無右孩子。

可以用歸納法證明其中的（2）和（3）：當i=1時，結論成立123(2)如果2i≤n，則結點i的左孩子的序號為2i；如果2i＞n，則結點i無左孩子。

(3)如果2i＋1≤n，則結點i的右孩子的序號為2i＋1；如果2i＋1＞n，則結點i無右孩子。假設：對于序號為j(1≤j≤i)的結點，當2×j≤n時，其左孩子存在且序號為2×j，當2×j>n時，其左孩子不存在；當2×j+1≤n時，其右孩子存在且序號為2×j+1，當2×j+1>n時，其右孩子不存在。(2)如果2i≤n，則結點i的左孩子的序號為2i；如果2i＞n，則結點i無左孩子。

(3)如果2i＋1≤n，則結點i的右孩子的序號為2i＋1；如果2i＋1＞n，則結點i無右孩子。j2j2j+1當i=j+1時，根據完全二叉樹的定義，若其左孩子存在，其左孩子結點的序號等于=2×i，且有2×i≤n；如果2×i>n，則左孩子不存在。若右孩子結點存在，右孩子結點的序號為2×i+1，且有2×i+1≤n；如果2×i+1>n，則右孩子不存在。故（2）和（3）得證。j2j2j+1i=j+12i2i+1由（2）和（3）我們可以很容易證明（1）。如果i＝1，則結點i是根結點，無雙親結點。如果i＞1，則結點i的雙親結點的序號為

[i/2]；

i2i2i+1118910456723對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則結點i的雙親結點為

i/2；結點i的左孩子為2i；結點i的右孩子為2i＋1。

性質5表明，在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。二叉樹的遍歷操作

二叉樹的遍歷是指從根結點出發(fā)，按照某種次序訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次。抽象操作，可以是對結點進行的各種處理，這里簡化為輸出結點的數(shù)據。二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結點。

考慮二叉樹的組成：根結點D左子樹L右子樹R二叉樹前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結點；②前序遍歷根結點的左子樹；③前序遍歷根結點的右子樹。前序遍歷序列：ABDGCEFABCDEFG中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結點的左子樹；②訪問根結點；③中序遍歷根結點的右子樹。

中序遍歷序列：DGBAECFABCDEFG后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結點的左子樹；②后序遍歷根結點的右子樹。③訪問根結點；后序遍歷序列：GDBEFCAABCDEFG層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

層序遍歷序列：ABCDEFGABCDEFG--/+*abcdef二叉樹遍歷操作練習前序遍歷結果：-+a*b-cd/ef中序遍歷結果：a+b*c-d-e/f后序遍歷結果：abcd-*+ef/-6.3常見的幾種算法查找算法排序算法枚舉、遞推、貪心、分治等算法查找算法順序查找算法折半查找算法順序查找是指從數(shù)組的一端開始，依次將要查找的數(shù)據元素與數(shù)組中的數(shù)據元素進行比較的過程。折半查找在有序表中（low,high,low<=high），取中間記錄作為比較對象，若給定值與中間記錄的關鍵碼相等，則查找成功；若給定值小于中間記錄的關鍵碼，則在中間記錄的左半區(qū)繼續(xù)查找；若給定值大于中間記錄的關鍵碼，則在中間記錄的右半區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。折半查找的基本思想

[r1………rmid-1]rmid[rmid+1………rn]

如果k<rmid

如果k>rmid查找左半區(qū)查找右半區(qū)k（mid=(1+n)/2）例：查找值為14的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>high排序：給定一組記錄的集合{r1,r2,……,rn}，其相應的關鍵碼分別為{k1,k2,……,kn}，排序是將這些記錄排列成順序為{rs1,rs2,……,rsn}的一個序列，使得相應的關鍵碼滿足ks1≤ks2≤……≤ksn（稱為升序）或ks1≥ks2≥……≥ksn（稱為降序）。正序：待排序序列中的記錄已按關鍵碼排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。趟：在排序過程中，將待排序的記錄序列掃描一遍稱為一趟。 通常，一次排序過程需要進行多趟掃描才能完成排序的基本概念排序的分類-根據排序過程中所進行的基本操作分：1.基于比較：基本操作——關鍵碼的比較和記錄的移動，其最差時間下限已經被證明為O（nlog2n）。2.

不基于比較：根據關鍵碼的分布特征。比如，桶式排序，基數(shù)排序（多關鍵字排序）排序的基本概念基于比較的內排序1.插入排序2.交換排序3.選擇排序4.歸并排序不基于比較的內排序1.分配排序 桶式排序 基數(shù)排序時間復雜性：基本操作。內排序在排序過程中的基本操作：⑴比較：關鍵碼之間的比較；⑵移動：記錄從一個位置移動到另一個位置。2.空間復雜性：

輔助存儲空間。輔助存儲空間是指在數(shù)據規(guī)模一定的條件下，除了存放待排序記錄占用的存儲空間之外，執(zhí)行算法所需要的其他存儲空間。排序算法的性能基本思想：在插入第i（i＞1）個記錄時，前面的i-1個記錄已經排好序。直接插入排序有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……基本思想：在插入第i（i＞1）個記錄時，前面的i-1個記錄已經排好序。（1）如何構造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序需解決的關鍵問題?直接插入排序過程示例

r0123456211825221025*212125i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5直接插入排序算法性能分析最好情況下（正序）：

12345時間復雜度為O(n)。比較次數(shù)：n-1移動次數(shù)：2(n-1)123451234512345123452345直接插入排序算法性能分析最好情況下（正序）：

比較次數(shù)：n-1移動次數(shù)：2(n-1)最壞情況下（逆序或反序）：時間復雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（時間復雜度為O(n)。平均情況下（隨機排列）：

直接插入排序算法性能分析時間復雜度為O(n2)。比較次數(shù)：移動次數(shù)：4)1)(4(-+=?nnn2=i4)1)(2(2-+=?=nnnii2（21+i）交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個記錄，將它們的關鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲位置。

交換排序反序則交換rirj交換類排序的兩種方法冒泡排序快速排序起泡排序基本思想：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。

rj

rj+1ri+1≤……

≤rn-1≤rn

無序區(qū)有序區(qū)1≤j≤i-1已經位于最終位置反序則交換05981269385381起泡排序過程示例

059812693853810598126938538105981269385381起泡排序的時間性能分析最好情況（正序）：比較次數(shù)：n-1移動次數(shù)：012345時間復雜度為O(n)。12345最壞情況（反序）：起泡排序的時間性能分析最好情況（正序）：比較次數(shù)：n-1移動次數(shù)：054321時間復雜度為O(n)；時間復雜度為O(n2)。43215321452134512345比較次數(shù)：移動次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時間復雜度為O(n2)。選擇排序的主要操作是選擇，其主要思想是：每趟排序在當前待排序序列中選出關鍵碼最小的記錄，添加到有序序列中。

有序序列r1r2ri-1rirnrk…………無序序列rnri+1r1r2ri-1……riri……交換最小記錄選擇排序簡單選擇排序示例0821i=2最小者08交換21,08最小者16交換25,16最小者21交換49,212128i=12516490808i=3210828492128491625161625i=4最小者25交換25,28i=5最小者28不交換簡單選擇排序示例492108281625254921081628252849210816282528無序區(qū)只有一個記錄歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個有序序列。

歸并排序歸并：將兩個或兩個以上的有序序列合并成一個有序序列的過程。二路歸并排序60203154455652060531445565

60203154455655203160

4455655203144556065二路歸并排序算法的性能分析時間性能：一趟歸并操作是將r[1]~r[n]中相鄰的長度為h的有序序列進行兩兩歸并，并把結果存放到r1[1]~r1[n]中，這需要O(n)時間。整個歸并排序需要進行趟，因此，總的時間代價是O(nlog2n)。這是歸并排序算法的最好、最壞、平均的時間性能。空間性能：算法在執(zhí)行時，需要占用與原始記錄序列同樣數(shù)量的存儲空間，因此空間復雜度為O(n)。éùn2log桶式排序假設待排序的記錄的值在0~m-1之間設置m個桶，依次掃描待排序的記錄，R[1]，…，R[n-1]，把關鍵字等于k的記錄全都裝入到第k個箱子里(分配)，然后按序號依次將各非空的箱子首尾連接起來(收集)。

3151321526338分/p>

680123456789收集1313233515268桶式排序分析特點：需要較多的桶時間復雜性一次分配，O(n)一次收集，O(m)O(n+m)空間復雜性O(m)基數(shù)排序每張撲克牌有兩個“關鍵碼”：花色和面值。其有序關系為：

花色：

面值：2

<3<4<5<6<7<8<9<10<J<Q<K<A基數(shù)排序“花色”優(yōu)先及高于“面值”方法一：先按花色分成4堆；然后，每堆再按“面值”排；最后，收成一堆。

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K“花色”優(yōu)先及高于“面值”方法二？ 先按面值分成13堆；收成一堆。再按花色分成四堆，最后，收成一堆。A

2

3

4

5

6

7

8

9

10

J

Q

K

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K基數(shù)排序基數(shù)排序（低位優(yōu)先）基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵碼進行排序。基本思想從關鍵字的最“低位”開始，將關鍵字分配到r(基數(shù)）個堆（桶）中；按桶的編號將關鍵字收集起來；然后，以“次低位”將關鍵字又分配到r個桶中；再收集，……，重復直到“