[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第1章 緒論.ppt

1、1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 1.4 算法和算法分析算法和算法分析 1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn) 2 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 用計(jì)算機(jī)解決具體問(wèn)題的步驟用計(jì)算機(jī)解決具體問(wèn)題的步驟 ： 1. 抽象出一個(gè)抽象出一個(gè)數(shù)學(xué)模型數(shù)學(xué)模型； 2. 設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法算法； 3. 編程、測(cè)試、調(diào)整。編程、測(cè)試、調(diào)整。 尋求數(shù)學(xué)模型：尋求數(shù)學(xué)模型：分析分析問(wèn)題問(wèn)題、提取、提取操作操作的的對(duì)象對(duì)象及其及其 對(duì)象之間的對(duì)象之間的關(guān)系關(guān)系并進(jìn)行描述。并進(jìn)行描述。非數(shù)值計(jì)算非數(shù)值計(jì)算 操作對(duì)象操作對(duì)象關(guān)系和操作

2、關(guān)系和操作 3 1.2 基本概念 數(shù)據(jù)數(shù)據(jù)： 指所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算指所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算 機(jī)處理的機(jī)處理的。 是計(jì)算機(jī)操作的是計(jì)算機(jī)操作的。 數(shù)據(jù)元素?cái)?shù)據(jù)元素: : 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的單位。單位。 在計(jì)算機(jī)程序中作為一個(gè)在計(jì)算機(jī)程序中作為一個(gè)“”進(jìn)行考進(jìn)行考 慮。慮。 一一. . 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 4 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)： 是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的的的單位。單位。 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: : 是是的數(shù)據(jù)元素的集合，如的數(shù)據(jù)元素的集合，如:一個(gè)班級(jí)一個(gè)班級(jí) 的成績(jī)表可以看作一個(gè)數(shù)據(jù)對(duì)象。它是的成績(jī)表可以看作一個(gè)數(shù)據(jù)對(duì)象。它是數(shù)據(jù)數(shù)據(jù)

3、的一個(gè)的一個(gè) 子集子集。 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 若在特性相同的數(shù)據(jù)元素若在特性相同的數(shù)據(jù)元素集合集合中的中的數(shù)據(jù)元素?cái)?shù)據(jù)元素之間存之間存 在一種或多種在一種或多種特定的關(guān)系特定的關(guān)系，則稱該數(shù)據(jù)元素的集合，則稱該數(shù)據(jù)元素的集合 為為“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)“。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是帶是帶“結(jié)構(gòu)結(jié)構(gòu)”的的數(shù)據(jù)元素?cái)?shù)據(jù)元素的集合。的集合。 5 數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組是一個(gè)二元組 Data_Structures = (D, S) 其中其中: D 是是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是是 D上關(guān)系的有限集。上關(guān)系的有限集。 6 二二. . 數(shù)據(jù)類型數(shù)據(jù)類型 在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，必須對(duì)程序中出現(xiàn)

4、在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，必須對(duì)程序中出現(xiàn) 的每個(gè)的每個(gè)變量、常量或表達(dá)式變量、常量或表達(dá)式，明確說(shuō)明它們，明確說(shuō)明它們所屬的數(shù)所屬的數(shù) 據(jù)類型據(jù)類型。 【例】【例】C/C+語(yǔ)言中提供的基本數(shù)據(jù)類型有語(yǔ)言中提供的基本數(shù)據(jù)類型有: 整整 型型 int浮浮 點(diǎn)點(diǎn) 型型 float 字符型字符型 char 邏輯型邏輯型 bool （ C+語(yǔ)言）語(yǔ)言） 雙精度型雙精度型 double 1.2 基本概念 7 8 三三. . 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 (Abstract Data Type , ADT) 抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型：是指一個(gè)是指一個(gè)數(shù)學(xué)模型數(shù)學(xué)模型以及定義在此數(shù)以及定義在此數(shù) 學(xué)模型上

5、的學(xué)模型上的一組操作一組操作。 即：即：ADT的定義由一個(gè)的定義由一個(gè)值域值域和定義在該值域上的一和定義在該值域上的一 組組操作操作組成。組成。 ADT的定義僅取決于的定義僅取決于數(shù)據(jù)模型數(shù)據(jù)模型的的邏輯特征邏輯特征。 ADT和和數(shù)據(jù)類型數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。實(shí)質(zhì)上是一個(gè)概念。 與其在與其在計(jì)算機(jī)內(nèi)部計(jì)算機(jī)內(nèi)部的表示和實(shí)現(xiàn)無(wú)關(guān)。的表示和實(shí)現(xiàn)無(wú)關(guān)。 “抽象抽象”的意義在于數(shù)據(jù)類型的的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性數(shù)學(xué)抽象特性。 不論內(nèi)部結(jié)構(gòu)如何變化，都不論內(nèi)部結(jié)構(gòu)如何變化，都不會(huì)影響外部使用不會(huì)影響外部使用。 9 例：線性表這樣的抽象數(shù)據(jù)類型。例：線性表這樣的抽象數(shù)據(jù)類型。 數(shù)學(xué)模型數(shù)學(xué)模型

6、：數(shù)據(jù)元素的集合；：數(shù)據(jù)元素的集合； 該集合內(nèi)的元素的該集合內(nèi)的元素的關(guān)系關(guān)系：除第一個(gè)和最后：除第一個(gè)和最后 一個(gè)外，每個(gè)元素有唯一的前趨和唯一的一個(gè)外，每個(gè)元素有唯一的前趨和唯一的 后繼；后繼； 操作操作：插入一個(gè)元素、刪除一個(gè)元素等。：插入一個(gè)元素、刪除一個(gè)元素等。 10 抽象數(shù)據(jù)類型不僅僅局限于抽象數(shù)據(jù)類型不僅僅局限于固有數(shù)據(jù)類型固有數(shù)據(jù)類型，也包括，也包括用用 戶自定義的戶自定義的數(shù)據(jù)類型。數(shù)據(jù)類型。 ADT 按照其值的不同特性，分為按照其值的不同特性，分為4種類型：種類型： 原原 子子 類類 型型：其值其值不可分解的類型；如：不可分解的類型；如：int 固定聚合類型固定聚合類型：其

7、值由確定數(shù)目的成分按某種結(jié)構(gòu)組成；如：其值由確定數(shù)目的成分按某種結(jié)構(gòu)組成；如： 復(fù)數(shù)；復(fù)數(shù)； 可變聚合類型可變聚合類型：其值由不固定數(shù)目的成分按某種結(jié)構(gòu)組成；其值由不固定數(shù)目的成分按某種結(jié)構(gòu)組成； 如：學(xué)生基本情況，有序整數(shù)序列；如：學(xué)生基本情況，有序整數(shù)序列； 多形數(shù)據(jù)類型多形數(shù)據(jù)類型：其值的成分不確定的數(shù)據(jù)類型；（元素之間其值的成分不確定的數(shù)據(jù)類型；（元素之間 的關(guān)系相同，基本操作也相同的關(guān)系相同，基本操作也相同 ） 11 2. 數(shù)據(jù)封裝：數(shù)據(jù)封裝：將實(shí)體的將實(shí)體的外部特性外部特性和其內(nèi)部和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)實(shí)現(xiàn)細(xì)節(jié) 分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)

8、節(jié)。 1. 數(shù)據(jù)抽象：數(shù)據(jù)抽象：用用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào) 的是其的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的、其所能完成的功能功能以及它和外以及它和外 部用戶的部用戶的接口接口（即外界使用它的方法）。（即外界使用它的方法）。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的定義由一個(gè)的定義由一個(gè)值域值域和定義在該值域上和定義在該值域上 的一組的一組操作操作組成。組成。 12 抽象數(shù)據(jù)類型可用三元組表示抽象數(shù)據(jù)類型可用三元組表示: ADT =（D，S，P） 其中：其中：D 是是數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象； S 是是 D 上的上的關(guān)系關(guān)系集；集； P 是是對(duì)對(duì) D 的的基本操作基本操作集集。 1

9、3 數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組是一個(gè)二元組 Data_Structures = (D, S) 其中其中: D 是是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集， S 是是 D上關(guān)系的有限集。上關(guān)系的有限集。 14 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)對(duì)象的定義-D 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義-S 基本操作：基本操作：基本操作的定義基本操作的定義-P ADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 基本操作基本操作的定義格式為的定義格式為: 基本操作名基本操作名（參數(shù)表參數(shù)表） 初始條件初始條件：初始條件描述：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述操作結(jié)果描

10、述 其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的 定義用定義用偽碼描述偽碼描述 15 1.1.參數(shù)表：參數(shù)表： 賦值參數(shù)賦值參數(shù): : 只為操作提供只為操作提供輸入值輸入值。 引用參數(shù)引用參數(shù): : 以以 sum.imagpart = z1.imagpart + z2.imagpart; 其它省略其它省略 23 1.3 算法和算法的衡量 一一. 算法算法 算法算法: :算法是對(duì)算法是對(duì)特定問(wèn)題特定問(wèn)題求解步驟求解步驟的一種描述的一種描述, , 是指是指 令的令的有限序列有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。，其中每一條指令表示一個(gè)或多個(gè)操作。 一個(gè)算法必須滿足以下五個(gè)重要一個(gè)算法

11、必須滿足以下五個(gè)重要特性特性： 1有窮性有窮性 2確定性確定性 3可行性可行性 4有輸入有輸入 5有輸出有輸出 24 1 1有窮性有窮性: : 對(duì)于任意一組合法輸入值，在執(zhí)行對(duì)于任意一組合法輸入值，在執(zhí)行有窮有窮 步驟步驟之后一定能結(jié)束，且每一步驟都能在之后一定能結(jié)束，且每一步驟都能在有限時(shí)間有限時(shí)間 內(nèi)完成。內(nèi)完成。 2 2確定性確定性: : 對(duì)于對(duì)于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算下所應(yīng)執(zhí)行的操作，在算 法中都有法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都的規(guī)定，使算法的執(zhí)行者或閱讀者都 能明確其含義及如何執(zhí)行。并且在任何條件下，算能明確其含義及如何執(zhí)行。并且在任何條件下，算 法

12、都只有一條執(zhí)行路徑。法都只有一條執(zhí)行路徑。 3 3可行性可行性: : 算法中描述的操作都是可以通過(guò)算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)已經(jīng)實(shí) 現(xiàn)現(xiàn)的的基本運(yùn)算基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。執(zhí)行有限次來(lái)實(shí)現(xiàn)。 25 4 4有輸入：有輸入：零個(gè)或多個(gè)的輸入。零個(gè)或多個(gè)的輸入。作為算法加工對(duì)象作為算法加工對(duì)象 的量值，通常體現(xiàn)為算法中的一組變量。有些輸入的量值，通常體現(xiàn)為算法中的一組變量。有些輸入 量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上 可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中?？梢詻](méi)有輸入，實(shí)際上已被嵌入算法之中。 5 5有輸出：有輸出：一個(gè)或多個(gè)的輸出。一

13、個(gè)或多個(gè)的輸出。它是一組與它是一組與“輸輸 入入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得有確定關(guān)系的量值，是算法進(jìn)行信息加工后得 到的結(jié)果，這種確定關(guān)系即為算法的功能。到的結(jié)果，這種確定關(guān)系即為算法的功能。 26 有窮性？有窮性？ 不是一個(gè)算法！不是一個(gè)算法！ 27 二二. 算法設(shè)計(jì)的原則算法設(shè)計(jì)的原則 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)： 1正確性正確性 2. 可讀性可讀性 3健壯性健壯性 4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求 28 1 1正確性正確性 算法應(yīng)當(dāng)滿足以特定的算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明規(guī)格說(shuō)明”方式給出的方式給出的 需求需求。 對(duì)

14、算法是否對(duì)算法是否“正確正確”的理解可以有以下四個(gè)層次：的理解可以有以下四個(gè)層次： a程序中不含程序中不含語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤； b程序?qū)τ诔绦驅(qū)τ趲捉M輸入數(shù)據(jù)幾組輸入數(shù)據(jù)能夠得出滿足要求的能夠得出滿足要求的 結(jié)果；結(jié)果； c程序?qū)τ诔绦驅(qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y精心選擇的、典型、苛刻且?guī)в械箅y 性的性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d程序?qū)τ诔绦驅(qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)一切合法的輸入數(shù)據(jù)都能得出滿足要都能得出滿足要 求的結(jié)果；求的結(jié)果； 通常以第通常以第 c 層意義的正確性作為衡量標(biāo)準(zhǔn)。層意義的正確性作為衡量標(biāo)準(zhǔn)。 29 2. 2. 可讀性可讀

15、性 算法主要是為了人的閱讀與交流，其次才是為計(jì)算算法主要是為了人的閱讀與交流，其次才是為計(jì)算 機(jī)執(zhí)行，因此算法應(yīng)該機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解易于人的理解； 另一方面，難讀的程序易于另一方面，難讀的程序易于隱藏較多錯(cuò)誤隱藏較多錯(cuò)誤而難以調(diào)而難以調(diào) 試。試。 3 3健壯性健壯性 當(dāng)輸入的當(dāng)輸入的數(shù)據(jù)非法數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从硶r(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从?或進(jìn)行相應(yīng)處理，而不是產(chǎn)生或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果莫名奇妙的輸出結(jié)果 處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是 返回一個(gè)返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值表示錯(cuò)誤或錯(cuò)誤性質(zhì)

16、的值，以便進(jìn)行處理，以便進(jìn)行處理 30 4 4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求 通常，效率指的是算法通常，效率指的是算法執(zhí)行時(shí)間執(zhí)行時(shí)間；存儲(chǔ)量指的是算；存儲(chǔ)量指的是算 法執(zhí)行過(guò)程中所需的法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間最大存儲(chǔ)空間，兩者都與問(wèn)題，兩者都與問(wèn)題 的規(guī)模有關(guān)。的規(guī)模有關(guān)。 31 算法與程序的區(qū)別算法與程序的區(qū)別 算法算法是解決問(wèn)題的一種方法或一個(gè)過(guò)程，考慮是解決問(wèn)題的一種方法或一個(gè)過(guò)程，考慮 如何將輸入轉(zhuǎn)換成輸出，一個(gè)問(wèn)題可以有如何將輸入轉(zhuǎn)換成輸出，一個(gè)問(wèn)題可以有多個(gè)多個(gè) 算法。算法。 程序程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。算法的具體實(shí)現(xiàn)。 主

17、要區(qū)別：主要區(qū)別：有窮性、正確性和描述方法有窮性、正確性和描述方法 程序可以是程序可以是無(wú)窮無(wú)窮的，例如的，例如OS，算法是，算法是有窮有窮的；的； 程序可以是程序可以是錯(cuò)誤錯(cuò)誤的，而算法必須是的，而算法必須是正確正確的；的； 程序是用程序是用程序設(shè)計(jì)語(yǔ)言描述程序設(shè)計(jì)語(yǔ)言描述的，在機(jī)器上可以的，在機(jī)器上可以 執(zhí)行，算法還可以用執(zhí)行，算法還可以用自然語(yǔ)言、框圖、高級(jí)程自然語(yǔ)言、框圖、高級(jí)程 序語(yǔ)言序語(yǔ)言等方式描述。等方式描述。 32 三三. 算法效率的衡量方法和準(zhǔn)則算法效率的衡量方法和準(zhǔn)則 事后統(tǒng)計(jì)事后統(tǒng)計(jì) 缺點(diǎn)：缺點(diǎn)：1必須執(zhí)行程序必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì)其它因素掩蓋算法本質(zhì) 33

18、 和算法執(zhí)行時(shí)間相關(guān)的和算法執(zhí)行時(shí)間相關(guān)的因素因素： 算法選用的策略算法選用的策略 問(wèn)題的規(guī)模問(wèn)題的規(guī)模 編寫(xiě)程序的語(yǔ)言編寫(xiě)程序的語(yǔ)言 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 計(jì)算機(jī)執(zhí)行指令的速度計(jì)算機(jī)執(zhí)行指令的速度 事前分析事前分析 34 35 36 37 算法算法 = 控制結(jié)構(gòu)控制結(jié)構(gòu) + 原操作原操作（固有數(shù)據(jù)類型的操作）（固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 = （原操作（原操作(i)的的執(zhí)行次數(shù)執(zhí)行次數(shù)原操作原操作(i)的的執(zhí)行時(shí)間執(zhí)行時(shí)間） 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)原操作執(zhí)行次數(shù)之和之和 成正比成正比 通常，從算法中選取通常

19、，從算法中選取一種一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)對(duì)于所研究的問(wèn)題來(lái)說(shuō) 是是 基本操作基本操作 的原操作，以該的原操作，以該基本操作基本操作 在算法中重在算法中重 復(fù)執(zhí)行的次數(shù)復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時(shí)間的作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則衡量準(zhǔn)則。 38 例:求下列程序段各語(yǔ)句的頻度頻度。 (1)for(i=1; i=n;i(1)for(i=1; i=n;i+) n+1+) n+1 x+; n x+; n (2) (2) for(j=1;j=n;jfor(j=1;j=n;j+) n+) n+1+1 for(k=1;k=n;k for(k=1;k=n;k+) n+) n* *(n(n+1+1) ) x+;

20、n x+; n* *n n 39 (1) i=1; k=0; while (i=n-1) k+=10*i; i+; 語(yǔ)句頻度語(yǔ)句頻度T(n) i=1; k=0; do k+=10*i; i+; while (i=n-1) (2) 語(yǔ)句頻度語(yǔ)句頻度T(n) =n-1 =n-1 40 (3) k=0; for(i=1;i=n;i+) for(j=i;j=n;j+) k+; i=1時(shí)；時(shí)；j循環(huán)循環(huán)n次次 i=2時(shí)；時(shí)；j循環(huán)循環(huán)n-1次次 i=n時(shí)；時(shí)；j循環(huán)循環(huán)1次次 語(yǔ)句頻度語(yǔ)句頻度T(n) =n+(n-1)+1 =(n-1+1)*(n+1)/2 41 【例】?jī)蓚€(gè)【例】?jī)蓚€(gè)NN矩陣相乘矩陣相乘

21、 void mult(int a, int b, int i=n; +i) / n+1 for (j=1; j=n; +j) /n*(n+1) ci,j = 0; /n*n for (k=1; k1 - -i) /n-1次次 change = FALSE; / change 為元素進(jìn)行交換標(biāo)志為元素進(jìn)行交換標(biāo)志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / (n-2)*i / 一趟起泡一趟起泡 / bubble_sort 基本操作基本操作:比較操作比較操作 時(shí)間復(fù)雜度時(shí)間復(fù)雜度: O(n2) 43 1i 0j 1 1n 2 )n(T i 1n 2 )1.111( i 1n 2 )101i ( i 1n 2 i i