第二版本章要點(diǎn)：5.1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)5.2常用的數(shù)據(jù)結(jié)構(gòu)5.3Python序列數(shù)據(jù)概述5.4序列數(shù)據(jù)的基本操作5.5列表5.6元組5.7集合5.8字典（映射）5.9算法基礎(chǔ)5.10常用的查找和排序算法5.11應(yīng)用舉例第5章組合數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)5.1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)著名的計(jì)算機(jī)科學(xué)家尼克勞斯?沃思（NikiklausWirth）指出：程序=算法+數(shù)據(jù)結(jié)構(gòu)算法是執(zhí)行特定任務(wù)的方法數(shù)據(jù)結(jié)構(gòu)是一種存儲(chǔ)數(shù)據(jù)的方式，有助于求解特定的問題組成數(shù)據(jù)元素的項(xiàng)稱之為數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小標(biāo)識(shí)單位，又稱為字段（Field）或者域（Field）例如，學(xué)生信息由學(xué)號(hào)、姓名、性別、出生年月、專業(yè)等組成數(shù)據(jù)（Data）是能夠被計(jì)算機(jī)處理的對(duì)象集合。數(shù)據(jù)由數(shù)據(jù)元素（DateElement）組成，數(shù)據(jù)元素包含數(shù)據(jù)項(xiàng)（DataItem）在學(xué)生檔案管理系統(tǒng)中，每位學(xué)生信息是數(shù)據(jù)的基本單位，稱之為數(shù)據(jù)元素，也稱為元素（Element）、節(jié)點(diǎn)（Node）或者記錄（Record）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算結(jié)構(gòu)數(shù)據(jù)的運(yùn)算結(jié)構(gòu)反映在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，例如檢索、插入、刪除、更新和排序等數(shù)據(jù)結(jié)構(gòu)通常由三個(gè)部分組成：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)主要包括線性結(jié)構(gòu)（一對(duì)一的關(guān)系）、樹形結(jié)構(gòu)（一對(duì)多的關(guān)系）、圖形結(jié)構(gòu)（多對(duì)多的關(guān)系）、集合等數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)反映數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式，即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。其具體的實(shí)現(xiàn)方法包括順序、鏈接、索引、散列等多種形式。一種數(shù)據(jù)結(jié)構(gòu)可以由一種或者多種物理存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)010302數(shù)據(jù)的邏輯結(jié)構(gòu)（1）線性表、隊(duì)列、棧等數(shù)據(jù)結(jié)構(gòu)屬于線性結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無關(guān)數(shù)據(jù)結(jié)構(gòu)可以表示為DS=(D,R)，其中DS表示數(shù)據(jù)結(jié)構(gòu)，D表示數(shù)據(jù)集合，R表示關(guān)系（Relation）集合三口之家的成員的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示如下：DS=(D,R)D={父親,母親,孩子}R={(父親,母親),(父親,孩子),(母親,孩子)}數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)中的元素節(jié)點(diǎn)具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述，線性結(jié)構(gòu)具有以下特點(diǎn)。（1）線性結(jié)構(gòu)是非空集。（2）線性結(jié)構(gòu)有且僅有一個(gè)開始節(jié)點(diǎn)和一個(gè)終端節(jié)點(diǎn)。（3）線性結(jié)構(gòu)所有節(jié)點(diǎn)都最多只有一個(gè)直接前趨節(jié)點(diǎn)和一個(gè)直接后繼節(jié)點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)（2）

常用的數(shù)據(jù)邏輯結(jié)構(gòu)包括如下幾種方式，如圖所示。（1）集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合”的相互關(guān)系外，別無其他關(guān)系。（2）線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系。（3）樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系。（4）圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系非線性結(jié)構(gòu)中的各元素節(jié)點(diǎn)之間具有多個(gè)對(duì)應(yīng)關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述，非線性結(jié)構(gòu)具有以下特點(diǎn)。（1）非線性結(jié)構(gòu)是非空集。（2）非線性結(jié)構(gòu)的一個(gè)節(jié)點(diǎn)可能有多個(gè)直接前趨節(jié)點(diǎn)和多個(gè)直接后繼節(jié)點(diǎn)。在實(shí)際應(yīng)用中，數(shù)組、廣義表、樹結(jié)構(gòu)和圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)屬于非線性結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方式，它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示實(shí)現(xiàn)邏輯數(shù)據(jù)結(jié)構(gòu)的常用方法包括順序、鏈接、索引、散列等。一種邏輯數(shù)據(jù)結(jié)構(gòu)可以表示成一種或者多種物理存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)內(nèi)部的存儲(chǔ)結(jié)構(gòu)通常有兩種方式：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序映像借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系非順序映像借助指示元素存儲(chǔ)位置的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系常用算法

基于數(shù)據(jù)結(jié)構(gòu)的常用算法包括以下幾種。（1）檢索：在數(shù)據(jù)結(jié)構(gòu)中查找滿足給定條件的節(jié)點(diǎn)。（2）插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點(diǎn)。（3）刪除：從數(shù)據(jù)結(jié)構(gòu)中刪除指定節(jié)點(diǎn)。（4）更新：改變指定節(jié)點(diǎn)的一個(gè)或者多個(gè)字段的值。（5）排序：按某種指定的順序重新排列節(jié)點(diǎn)（從而可以提高其他算法的操作效率）數(shù)據(jù)的算法基于數(shù)據(jù)的邏輯結(jié)構(gòu)，但具體實(shí)現(xiàn)要在物理存儲(chǔ)結(jié)構(gòu)上進(jìn)行5.2常用的數(shù)據(jù)結(jié)構(gòu)5.2.1線性表5.2.2隊(duì)列5.2.3棧5.2.4樹5.2.5圖5.2.6堆5.2.7散列表線性表線性表（LinearList）是最基本的一種數(shù)據(jù)結(jié)構(gòu)，是具有相同特性的數(shù)據(jù)元素的有限序列，通常記做(a1,a2,…,an）。其中a1無前趨，an無后繼，其他每個(gè)元素都有一個(gè)前趨和后繼線性表的物理存儲(chǔ)結(jié)構(gòu)主要有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，前者稱為順序表，后者稱為線性鏈表順序存儲(chǔ)結(jié)構(gòu)使用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素順序表的優(yōu)點(diǎn)是查找和訪問元素速度快，但插入和刪除開銷大鏈表（LinkedList）是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，這種存儲(chǔ)結(jié)構(gòu)具有在物理上存在非連續(xù)的特點(diǎn)鏈表由一序列數(shù)據(jù)節(jié)點(diǎn)構(gòu)成，每個(gè)數(shù)據(jù)節(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分線性鏈表的優(yōu)點(diǎn)在于插入和刪除效率高。其缺點(diǎn)是訪問元素時(shí)需要遍歷鏈表的所有元素，因而效率欠佳隊(duì)列和棧隊(duì)列（Queue）是先進(jìn)先出的序列（FIFO，F(xiàn)irstInFirstOut），即最先添加的元素，是最先彈出的元素列表可以實(shí)現(xiàn)隊(duì)列，但并不適合。因?yàn)閺牧斜淼念^部移除一個(gè)元素，列表中的所有元素都需要移動(dòng)位置，所以效率不高。用戶可以使用collections模塊中的deque對(duì)象來刪除列表頭部的元素棧（Stack）是后進(jìn)先出的隊(duì)列（LIFO，LastInFirstOut），即最后添加（push）的元素，是最先彈出（pop）的元素向列表最后位置添加元素和從最后位置移除元素非常方便和高效，故使用列表可以快捷高效地實(shí)現(xiàn)棧list.append()方法對(duì)應(yīng)于入棧操作（push）；list.pop()對(duì)應(yīng)于出棧操作（pop）樹（1）

樹的常用術(shù)語（1）（1）節(jié)點(diǎn)：每個(gè)元素稱為節(jié)點(diǎn)。（2）根節(jié)點(diǎn)：沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)。（3）節(jié)點(diǎn)的度（degree）：一個(gè)節(jié)點(diǎn)含有的子節(jié)點(diǎn)個(gè)數(shù)稱為該節(jié)點(diǎn)的度。（4）葉節(jié)點(diǎn)或終端節(jié)點(diǎn)（leaf）：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。（5）非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)（branch）：度不為0的節(jié)點(diǎn)。樹（Tree）是典型的非線性結(jié)構(gòu)，由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合，其形狀像一棵倒掛的樹

樹具有以下的特點(diǎn)。（1）每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)。（2）沒有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)（root）。（3）每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)。（4）除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹樹（2）

樹的常用術(shù)語（2）（6）雙親節(jié)點(diǎn)或父節(jié)點(diǎn)（parent）：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。（7）孩子節(jié)點(diǎn)或子節(jié)點(diǎn)（child）：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)。（8）兄弟節(jié)點(diǎn)（sibling）：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)。（9）樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度。（10）節(jié)點(diǎn)的層次（level）：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推（11）樹的高度或深度（depth）：樹中節(jié)點(diǎn)的最大層次。（12）堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟節(jié)點(diǎn)。（13）節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。（14）子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。（15）森林：m（m>=0）棵互不相交的樹的集合稱為森林。樹（3）（16）空樹?？占弦彩菢洌Q為空樹?？諛渲袥]有節(jié)點(diǎn)。（17）無序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹。（18）有序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹。（19）二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹。（20）滿二叉樹：如果一棵二叉樹只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這棵二叉樹為滿二叉樹。即，一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹每一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了最大值，即滿二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。如圖5-6（a）所示是一棵深度為3的滿二叉樹（21）完全二叉樹：滿二叉樹中葉子節(jié)點(diǎn)所在的層次中，如果自右向左連續(xù)缺少若干葉子節(jié)點(diǎn)，這樣的得到的二叉樹被稱為完全二叉樹。即，若設(shè)二叉樹的深度為k，除第k層外，其它各層（1～k-1）的節(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，而第k層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊，這就是一個(gè)完全二叉樹。如圖5-6（b）所示是一棵完全二叉樹。如圖5-6（c）所示是一棵非完全二叉樹。滿二叉樹是完全二叉樹的特殊形態(tài)。（22）哈夫曼樹（最優(yōu)二叉樹）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹樹的常用術(shù)語（3）二叉樹重要性質(zhì)二叉樹的遍歷（1）以上三種操作有六種遍歷方法：NLR、LNR、LRN、NRL、RNL、RLN二叉樹是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成二叉樹具有五種基本形態(tài)遍歷二叉樹，就是按一定的規(guī)則和順序遍歷二叉樹的所有節(jié)點(diǎn)，使每一個(gè)節(jié)點(diǎn)都被訪問一次，而且只被訪問一次在任一給定節(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作。（1）訪問節(jié)點(diǎn)本身（N）。（2）遍歷該節(jié)點(diǎn)的左子樹（L）。（3）遍歷該節(jié)點(diǎn)的右子樹（R）二叉樹的遍歷（2）NLR：前序遍歷（PreorderTraversal），又稱為先序遍歷。若二叉樹非空，則依次執(zhí)行如下操作。訪問根結(jié)點(diǎn)（N）遍歷左子樹（L）遍歷右子樹（R）LNR：中序遍歷（InorderTraversal）。若二叉樹非空，則依次執(zhí)行如下操作。遍歷左子樹（L）訪問根結(jié)點(diǎn)（N）遍歷右子樹（R）LRN：后序遍歷（PostorderTraversal）。若二叉樹非空，則依次執(zhí)行如下操作。遍歷左子樹（L）遍歷右子樹（R）訪問根結(jié)點(diǎn)（N）010302其前序遍歷順序?yàn)椋篈BCDFEG其中序遍歷順序?yàn)椋築AFDCEG其后序遍歷順序?yàn)椋築FDGECA圖、堆、散列表圖（Graph）是另一種非線性數(shù)據(jù)結(jié)構(gòu)。圖是由頂點(diǎn)集合V（Vertex）和邊集合E（Edge）組成的，定義為G=(V，E)在圖結(jié)構(gòu)中，數(shù)據(jù)節(jié)點(diǎn)一般稱為頂點(diǎn)，而邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，那么就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系堆（Heap）是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其中子節(jié)點(diǎn)與父節(jié)點(diǎn)是一種有序關(guān)系散列表（Hashtable，也叫哈希表）是把鍵值映射（映射函數(shù)）到表（散列表）的數(shù)據(jù)結(jié)構(gòu)，通過鍵值可以實(shí)現(xiàn)快速查找5.3Python序列數(shù)據(jù)概述數(shù)組將數(shù)據(jù)存儲(chǔ)在一個(gè)或多個(gè)數(shù)組中，通過索引下標(biāo)訪問并處理數(shù)組的元素Python內(nèi)置的序列數(shù)據(jù)類型元組（tuple）、列表（list）、字符串（str）和字節(jié)數(shù)據(jù)（bytes和bytearray）序列數(shù)據(jù)的基本操作（1）序列的長度、最大值、最小值、求和len()、max()、min()，獲取序列的長度、序列中元素最大值、序列中元素最小值sum()獲取列表或元組中各元素之和>>>t1=(1,2,3,4)>>>sum(t1)#輸出：1010>>>t2=(1,'a',2)>>>sum(t2)#TypeError:unsupportedoperandtype(s)for+:'int'and'str'>>>s='1234'>>>sum(s)

#TypeError:unsupportedoperandtype(s)for+:'int'and'str'【例5.1】序列數(shù)據(jù)的求和示例序列數(shù)據(jù)的基本操作（2）【例5.2】序列的長度、最大值、最小值操作示例>>>s='abcdefg'>>>len(s)7>>>max(s)'g'>>>min(s)'a'>>>s2=''>>>len(s2)0>>>t=(10,2,3)>>>len(t)3>>>max(t)10>>>min(t)2>>>t2=()>>>len(t2)0>>>lst=[1,2,9,5,4]>>>len(lst)5>>>max(lst)9>>>min(lst)1>>>lst2=[]>>>len(lst2)0>>>b=b'ABCD'>>>len(b)4>>>max(b)68>>>min(b)65>>>b2=b''>>>len(b2)0序列的索引訪問操作>>>s='abcdef'>>>s[0]'a'>>>s[2]'c'>>>s[-1]'f'>>>s[-3]'d'>>>t=('a','e','i','o','u')>>>t[0]'a'>>>t[1]'e'>>>t[-1]'u'>>>t[-5]'a'>>>lst=[1,2,3,4,5]>>>lst[0]1>>>lst[1,2,3,4,5]>>>lst[2]='a'>>>lst[-2]='b'>>>lst[1,2,'a','b',5]>>>b=b'ABCDEF'>>>b[0]65>>>b[1]66>>>b[-1]70>>>b[-2]69【例5.3】序列的索引訪問示例序列的切片操作【例5.4】序列的切片操作示例>>>s='abcdef'>>>s[1:3]'bc'>>>s[3:10]'def'>>>s[8:2]''>>>s[:]'abcdef'>>>s[:2]'ab'>>>s[::2]'ace'>>>s[::-1]'fedcba'>>>t=('a','e','i','o','u')>>>t[-2:-1]('o',)>>>t[-2:]('o','u')>>>t[-99:-5]()>>>t[-99:-3]('a','e')>>>t[::]('a','e','i','o','u')>>>t[1:-1]('e','i','o')>>>t[1::2]('e','o')>>>lst=[1,2,3,4,5]>>>lst[:2][1,2]>>>lst[:1]=[]>>>lst[2,3,4,5]>>>lst[:2][2,3]>>>lst[:2]='a'>>>lst[1:]='b'>>>lst['a','b']>>>dellst[:1]>>>lst['b']>>>b=b'ABCDEF'>>>b[2:2]b''>>>b[0:1]b'A'>>>b[1:2]b'B'>>>b[2:2]b''>>>b[-1:]b'F'>>>b[-2:-1]b'E'>>>b[0:len(b)]b'ABCDEF's[i:j]··或者··s[i:j:k]序列的連接和重復(fù)操作【例5.5】序列的連接和重復(fù)操作示例>>>s1='abc'>>>s2='xyz'>>>s1+s2'abcxyz'>>>s1*3'abcabcabc'>>>s1+=s2>>>s1'abcxyz'>>>s2*=2>>>s2'xyzxyz'>>>t1=(1,2)>>>t2=('a','b')>>>t1+t2(1,2,'a','b')>>>t1*2(1,2,1,2)>>>t1+=t2>>>t1(1,2,'a','b')>>>t2*=2>>>t2('a','b','a','b')>>>lst1=[1,2]>>>lst2=['a','b']>>>lst1+lst2[1,2,'a','b']>>>2*lst2['a','b','a','b']>>>lst1+=lst2>>>lst1[1,2,'a','b']>>>lst2*=2>>>lst2['a','b','a','b']>>>b1=b'ABC'>>>b2=b'XYZ'>>>b1+b2b'ABCXYZ'>>>b1*3b'ABCABCABC'>>>b1+=b2>>>b1b'ABCXYZ'>>>b2*=2>>>b2b'XYZXYZ's1+s2··或者··s*n··或者··n*s序列的成員關(guān)系操作>>>s='Good,better,best!'>>>'o'insTrue>>>'g'notinsTrue>>>s.count('e')3>>>s.index('e',10)10>>>t=('r','g','b')>>>'r'intTrue>>>'y'notintTrue>>>t.count('r')1>>>t.index('g')1>>>lst=[1,2,3,2,1]>>>1inlstTrue>>>2notinlstFalse>>>lst.count(1)2>>>lst.index(3)2>>>b=b'Oh,Jesus!'>>>b'O'inbTrue>>>b'o'notinbTrue>>>b.count(b's')2>>>b.index(b's')6【例5.6】序列中元素的存在性判斷示例????序列的比較運(yùn)算操作【例5.7】序列的比較運(yùn)算示例>>>s1='abc'>>>s2='abc'>>>s3='abcd'>>>s4='cba'>>>s1>s4False>>>s2<=s3True>>>s1==s2True>>>s1!=s3True>>>'a'>'A'True>>>'a'>=''True>>>t1=(1,2)>>>t2=(1,2)>>>t3=(1,2,3)>>>t4=(2,1)>>>t1<t4True>>>t1<=t2True>>>t1==t3False>>>t1!=t2False>>>t1>=t3False>>>t4>t3True>>>s1=['a','b']>>>s2=['a','b']>>>s3=['a','b','c']>>>s4=['c','b','a']>>>s1<s2False>>>s1<=s2True>>>s1==s2True>>>s1!=s3True>>>s1>=s3False>>>s4>s3True>>>b1=b'abc'>>>b2=b'abc'>>>b3=b'abcd'>>>b4=b'ABCD'>>>b1<b2False>>>b1<=b2True>>>b1==b2True>>>b1>=b3False>>>b3!=b4True>>>b4>b3False序列的排序操作【例5.8】序列的排序操作示例>>>s1='axd'>>>sorted(s1)['a','d','x']>>>s2=(1,4,2)>>>sorted(s2)[1,2,4]>>>sorted(s2,reverse=True)[4,2,1]>>>s3='abAC'>>>sorted(s3,key=str.lower)['a','A','b','C']內(nèi)置函數(shù)all()和any()all(iterable)#如果序列的所有值都為True，返回True；否則，返回Falseany(iterable)#如果序列的任意值為True，返回True；否則，返回False>>>any((1,2,0))True>>>all([1,2,0])False5.5列表使用列表字面量可以創(chuàng)建列表實(shí)例對(duì)象。列表字面量列表采用方括號(hào)中用逗號(hào)分隔的項(xiàng)目定義>>>list1=[];list2=[1];list3=["a","b","c"]>>>print(list1,list2,list3)#輸出：[][1]['a','b','c']【例5.9】使用列表字面量創(chuàng)建列表實(shí)例對(duì)象示例>>>list1=list();list2=list("abc");list3=list(range(3))>>>print(list1,list2,list3)#輸出：[]['a','b','c'][0,1,2]【例5.10】使用list對(duì)象創(chuàng)建列表實(shí)例對(duì)象示例用戶也可以通過創(chuàng)建list對(duì)象來創(chuàng)建列表list():創(chuàng)建一個(gè)空列表list(iterable):創(chuàng)建一個(gè)列表，包含的項(xiàng)目為可枚舉對(duì)象iterable中的元素列表的序列操作>>>s=[1,2,3,4,5,6]>>>s[1]='a'>>>s[1,'a',3,4,5,6]>>>s[2]=[]>>>s[1,'a',[],4,5,6]>>>dels[3]>>>s[1,'a',[],5,6]>>>s[:2][1,'a']>>>s[2:3]=[]>>>s[1,'a',5,6]>>>s[:1]=[]>>>s['a',5,6]>>>s[:2]='b'>>>s['b',6]>>>dels[:1]>>>s[6]索引訪問、切片操作、連接操作、重復(fù)操作、成員關(guān)系操作、比較運(yùn)算操作，以及求列表長度、最大值、最小值等【例5.11】列表的序列操作示例列表是可變對(duì)象s[下標(biāo)]=x·····#設(shè)置列表元素，x為任意對(duì)象dels[下標(biāo)]····#刪除列表元素s[i:j]=x······#設(shè)置列表內(nèi)容，x為任意對(duì)象，也可以是元組、列表dels[i:j]·····#移去列表一序列元素，等同于s[i:j]=[]s[i:j]=[]······#移去列表一序列元素列表對(duì)象的方法列表解析表達(dá)式>>>[i**2foriinrange(10)]#平方值[0,1,4,9,16,25,36,49,64,81]>>>[(i,i**2)foriinrange(10)]#序號(hào),平方值[(0,0),(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81)]>>>[iforiinrange(10)ifi%2==0]#取偶數(shù)[0,2,4,6,8]>>>[(x,y,x*y)forxinrange(1,4)foryinrange(1,4)ifx>=y]#二重循環(huán)[(1,1,1),(2,1,2),(2,2,4),(3,1,3),(3,2,6),(3,3,9)]【例5.12】列表解析表達(dá)式示例使用列表解析可以簡(jiǎn)單高效地處理一個(gè)可迭代對(duì)象，并生成結(jié)果列表。列表解析表達(dá)式的形式如下[exprfori1

in序列1...foriN

in序列N]：迭代序列里所有內(nèi)容，并計(jì)算生成列表[exprfori1

in序列1...foriN

in序列Nifcond_expr]：按條件迭代，并計(jì)算生成列表列表的排序內(nèi)置數(shù)據(jù)類型list中的方法sort()，把列表中的數(shù)據(jù)項(xiàng)按升序重新排列。>>>a=[59,12,77,64,72,69,46,89,31,9]>>>sorted(a)#輸出：[9,12,31,46,59,64,69,72,77,89]>>>a#輸出：[59,12,77,64,72,69,46,89,31,9]>>>a.sort(reverse=True)>>>a#輸出：[89,77,72,69,64,59,46,31,12,9]【例5.13】Python語言提供的排序算法示例sort(*,key=None,reverse=False)sorted(iterable,*,key=None,reverse=False)內(nèi)置函數(shù)sorted()則保持原列表不變，返回一個(gè)新的包含按升序排列的項(xiàng)的列表010302元組>>>t1=tuple()>>>t2=tuple("abc")>>>t3=tuple([1,2,3])>>>t4=tuple(range(3))>>>print(t1,t2,t3,t4)#輸出：()('a','b','c')(1,2,3)(0,1,2)【例5.14】使用tuple對(duì)象創(chuàng)建元組實(shí)例對(duì)象示例元組也可以通過創(chuàng)建tuple對(duì)象來創(chuàng)建tuple()······#創(chuàng)建一個(gè)空元組tuple(iterable)#創(chuàng)建一個(gè)元組，包含的項(xiàng)目為可枚舉對(duì)象iterable中的元素元組的定義x1,[x2,...,xn]··或者··（x1,[x2,...,xn]）一組有序序列，包含0個(gè)或多個(gè)對(duì)象引用元組的序列操作索引訪問、切片操作、連接操作、重復(fù)操作、成員關(guān)系操作、比較運(yùn)算操作，以及求元組長度、最大值、最小值等>>>t1=(1,2,3,4,5,6,7,8,9,10)>>>len(t1)#輸出：10>>>max(t1)#輸出：10>>>sum(t1)#輸出：55【例5.15】元組的序列操作示例集合集合數(shù)據(jù)類型是沒有順序的簡(jiǎn)單對(duì)象的聚集，且集合中元素不重復(fù)Python集合數(shù)據(jù)類型包括可變集合對(duì)象（set）和不可變集合對(duì)象（frozenset）集合的定義{}表示空的dict，因?yàn)閐ict也使用花括號(hào)定義?？占癁閟et()set()······#創(chuàng)建一個(gè)空的可變集合set(iterable)······#創(chuàng)建一個(gè)可變集合，包含的項(xiàng)目為可枚舉對(duì)象iterable中的元素frozenset()······#創(chuàng)建一個(gè)空的不可變集合【例5.16】創(chuàng)建集合對(duì)象示例>>>{1,2,1}{1,2}>>>{1,'a',True}{1,'a'}>>>{1.2,True}{True,1.2}>>>set()set()>>>frozenset()frozenset()>>>set('Hello'){'H','e','o','l'}>>>{'a',[1,2]}Traceback(mostrecentcalllast):File"<pyshell#13>",line1,in<module>{'a',[1,2]}TypeError:unhashabletype:'list'集合的運(yùn)算：并集、交集、差集和對(duì)稱差集【例5.17】集合的運(yùn)算示例>>>s1={1,2,3}>>>s2={2,3,4}>>>s1|s2{1,2,3,4}>>>s1&s2{2,3}>>>s1-s2{1}>>>s1^s2{1,4}>>>s1.union(s2){1,2,3,4}>>>ersection(s2){2,3}>>>s1.difference(s2){1}>>>s1.symmetric_difference(s2){1,4}可變集合的方法方法說明示例s1.update(s2,...)s1|=s2|...并集s1=s1∪s2∪…>>>s1.update(s2)#s1={1,2,3,4}ersection_update(s2,...)s1&=s2&...交集s1=s1∩s2∩…>>>ersection_update(s2)#s1={2,3}s1.difference_update(s2,...)s1-=s2-...差集s1=s1－s2－…>>>s1.difference_update(s2)#s1={1}s1.symmetric_difference_update(s2)s1^=s2對(duì)稱差集s1=s1△s2s1.symmetric_difference_update(s2)#s1={1,4}s.add(x)把對(duì)象x添加到集合s>>>s1.add('a')#s1={1,2,3,'a'}s.remove(x)從集合s中移除對(duì)象x。若不存在，則導(dǎo)致KeyError>>>s1.remove(1)#s1={2,3}s.discard(x)從集合s中移除對(duì)象x（如果存在的話）>>>s1.discard(3)#s1={1,2}s.pop()從集合s隨機(jī)彈出一個(gè)元素，如果s為空，則導(dǎo)致KeyError>>>s1.pop()#輸出：1。s1={2,3}s.clear()清空集合s>>>s1.clear()#s1=set()假設(shè)表中的示例基于“s1={1,2,3};s2={2,3,4}”字典（映射）字典（dict，或映射map）是一組鍵/值對(duì)的數(shù)據(jù)結(jié)構(gòu)。每個(gè)鍵對(duì)應(yīng)于一個(gè)值。在字典中，鍵不能重復(fù)。根據(jù)鍵可以查詢到值>>>hash(100)

#結(jié)果：100>>>hash(1.23)

#結(jié)果：530343892119149569>>>hash('abc')#結(jié)果：901130859749610928對(duì)象的哈希（hash）值【例5.18】對(duì)象的哈希（hash）值示例字典的鍵只能使用不可變的對(duì)象，但字典的值可以使用不可變或可變的對(duì)象字典的創(chuàng)建>>>{}{}>>>{'a':'apple','b':'boy'}{'a':'apple','b':'boy'}>>>dict(){}>>>dict({1:'food',2:'drink'}){1:'food',2:'drink'}>>>dict([('id','1001'),('name','Jenny')]){'id':'1001','name':'Jenny'}>>>dict(baidu='',google=''){'baidu':'','google':''}【例5.19】創(chuàng)建字典對(duì)象示例?????字典的訪問操作>>>d={1:'food',2:'drink'}>>>d{1:'food',2:'drink'}>>>d[1]'food'>>>d[3]='fruit'>>>d{1:'food',2:'drink',3:'fruit'}>>>deld[2]>>>d{1:'food',3:'fruit'}>>>d[2]Traceback(mostrecentcalllast):File"<pyshell#100>",line1,in<module>d[2]KeyError:2【例5.20】字典的訪問示例???字典對(duì)象的方法假設(shè)表中的示例基于d={1:'food',2:'drink',3:'fruit'}方法說明示例d.clear()刪除所有元素>>>d.clear();d#結(jié)果：{}d.copy()淺拷貝字典>>>d1=d.copy();id(d),id(d1)(2487537820800,2487537277976)d.get(k)返回鍵k對(duì)應(yīng)的值，如果key不存在，返回None>>>d.get(1),d.get(5)('food',None)d.get(k,v)返回鍵k對(duì)應(yīng)的值，如果key不存在，返回v>>>d.get(1,'無'),d.get(5,'無')('food','無')d.pop(k)如果鍵k存在，返回其值，并刪除該項(xiàng)目；否則導(dǎo)致KeyError>>>d.pop(1),d('food',{2:'drink',3:'fruit'})d.pop(k,v)如果鍵k存在，返回其值，并刪除該項(xiàng)目；否則返回v>>>d.pop(5,'無'),d('無',{1:'food',2:'drink',3:'fruit'})d.setdefault(k,v)如果鍵k存在，返回其值；否則添加項(xiàng)目k=v，v默認(rèn)為None>>>d.setdefault(1)#結(jié)果：'food'>>>d.setdefault(4);d{1:'food',2:'drink',3:'fruit',4:None}d.update([other])使用字典或鍵值對(duì)，更新或添加項(xiàng)目到字典d>>>d1={1:'食物',4:'書籍'}>>>d.update(d1);d{1:'食物',2:'drink',3:'fruit',4:'書籍'}5.9算法基礎(chǔ)算法是指解決問題的一種方法或一個(gè)過程。算法通常使用計(jì)算機(jī)程序來實(shí)現(xiàn)

算法的實(shí)現(xiàn)為若干指令的有窮序列，具有如下性質(zhì)。（1）輸入數(shù)據(jù)。算法可以接收用于處理的外部數(shù)據(jù)。（2）輸出結(jié)果。算法可以產(chǎn)生輸出結(jié)果。（3）確定性。算法的組成指令必須是準(zhǔn)確無歧義。（4）有限性。算法指令的執(zhí)行次數(shù)必須是有限的，執(zhí)行的時(shí)間也必須是有限的算法的性能分析包括時(shí)間性能分析和空間性能分析兩個(gè)方面算法的時(shí)間性能分析，又稱之為算法的時(shí)間復(fù)雜度(TimeComplexity)分析問題的規(guī)模（Size）即算法求解問題的輸入量

一個(gè)算法運(yùn)行的總時(shí)間取決于以下兩個(gè)主要因素。（1）每條語句的執(zhí)行時(shí)間成本。（2）每條語句的執(zhí)行次數(shù)（頻度）即一個(gè)算法所耗費(fèi)的時(shí)間等于算法中每條語句的執(zhí)行時(shí)間之和【例5.21】算法中語句的頻度之和（frequency.py）total=0foriinrange(n):forjinrange(n):total+=a[i][j]print(total)循環(huán)語句運(yùn)行了n*n次，總算法執(zhí)行語句頻度為n2+2增長量級(jí)增長量級(jí)用于描述函數(shù)的漸進(jìn)增長行為，一般使用大O符號(hào)表示。例如，2n、100n與n+1屬于相同的增長量級(jí)，記為O(n)，表示函數(shù)隨n線性增長算法的空間復(fù)雜度分析Python語言面向?qū)ο筇匦缘闹饕鷥r(jià)之一是內(nèi)存消耗。Python的內(nèi)存消耗與其在不同計(jì)算機(jī)上的實(shí)現(xiàn)有關(guān)。不同版本的Python有可能使用不同方法實(shí)現(xiàn)同一種數(shù)據(jù)類型確定一個(gè)Python程序內(nèi)存使用的典型方法是，先統(tǒng)計(jì)程序所使用對(duì)象的數(shù)量，然后根據(jù)對(duì)象的類型乘以各對(duì)象占用的字節(jié)數(shù)使用函數(shù)sys.getsizeof(x)，可以返回一個(gè)內(nèi)置數(shù)據(jù)類型x在系統(tǒng)中所占用的字節(jié)數(shù)>>>importsys>>>sys.getsizeof(100)#整數(shù)對(duì)象占用內(nèi)存大小。輸出：28>>>sys.getsizeof("1.23")#字符串對(duì)象占用內(nèi)存大小。輸出：53>>>sys.getsizeof(True)#布爾邏輯型對(duì)象占用內(nèi)存大小。輸出：28【例5.22】Python語言中對(duì)象占用內(nèi)存大小示例5.10常用的查找和排序算法5.10.1順序查找法5.10.2二分查找法5.10.3冒泡排序法5.10.4選擇排序法5.10.5插入排序法5.10.6歸并排序法5.10.7快速排序法順序查找法假定要從n個(gè)元素中查找x的值是否存在，最原始的辦法是從頭到尾逐個(gè)查找，這種查找方法稱為順序查找法算法的時(shí)間復(fù)雜度為O(n)：最好的情況下，第一個(gè)項(xiàng)就是我們要找的數(shù)據(jù)對(duì)象，只有一次比較；最差的情況下，需要n次比較，全部比較完之后查不到數(shù)據(jù)；平均情況下，比較次數(shù)為n/2次【例5.23】在列表中順序查找特定數(shù)值x（sequentialSearch.py）……tobecontinued【例5.23】在列表中順序查找特定數(shù)值x（sequentialSearch.py）defsequentialSearch(alist,item):#順序查找法pos=0#初始查找位置found=False#未找到數(shù)據(jù)對(duì)象whilepos<len(alist)andnotfound:#列表未結(jié)束并且還未找到則一直循環(huán)ifalist[pos]==item:#找到匹配對(duì)象，返回Truefound=Trueelse:#否則查找位置+1pos=pos+1returnfounddefmain():testlist=[1,3,33,8,37,29,32,15,5]#測(cè)試數(shù)據(jù)列表print(sequentialSearch(testlist,3))#查找數(shù)據(jù)3print(sequentialSearch(testlist,13))#查找數(shù)據(jù)13if__name__=='__main__':main()程序運(yùn)行結(jié)果如下TrueFalse二分查找法二分查找法又稱折半查找法，用于預(yù)排序列表的查找問題要在排序列表a中查找元素t，首先，將列表alist中間位置的項(xiàng)與查找關(guān)鍵字t比較，如果兩者相等，則查找成功；否則利用中間項(xiàng)將列表分成前、后兩個(gè)子表，如果中間位置項(xiàng)目大于t，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，即查找成功；或直到子表不存在為止，即查找不成功對(duì)于包含N個(gè)元素的表，其時(shí)間復(fù)雜度為O(log2N)【例5.24】二分查找法的遞歸實(shí)現(xiàn)（binarySearch.py）……tobecontinued【例5.24】二分查找法的遞歸實(shí)現(xiàn)def_binarySearch(key,a,lo,hi):ifhi<=lo:return-1#查找失敗，返回-1mid=(lo+hi)//2#計(jì)算中間位置ifa[mid]>key:#中間位置項(xiàng)目大于查找關(guān)鍵字return_binarySearch(key,a,lo,mid)#遞歸查找前一子表elifa[mid]<key:#中間位置項(xiàng)目小于查找關(guān)鍵字return_binarySearch(key,a,mid+1,hi)#遞歸查找后一子表else:#中間位置項(xiàng)目等于查找關(guān)鍵字returnmid#查找成功，返回下標(biāo)位置defbinarySearch(key,a):#二分查找return_binarySearch(key,a,0,len(a))#遞歸二分查找法defmain():a=[1,13,26,33,45,55,68,72,83,99]print("關(guān)鍵字位于列表索引",binarySearch(33,a))#二分查找關(guān)鍵字33print("關(guān)鍵字位于列表索引",binarySearch(58,a))#二分查找關(guān)鍵字58if__name__=='__main__':main()程序運(yùn)行結(jié)果如下：關(guān)鍵字位于列表索引3關(guān)鍵字位于列表索引-1冒泡排序法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的冒泡法的算法如下：第1輪比較：從第一個(gè)元素開始，對(duì)列表中所有N個(gè)元素進(jìn)行兩兩大小比較，如果不滿足升序關(guān)系，則交換。即A[0]與A[1]比較，若A[0]>A[1]，則A[0]與A[1]交換；然后A[1]與A[2]比較，若A[1]>A[2]，則A[1]與A[2]交換；……直至最后A[N-2]與A[N-1]比較，若A[N-2]>A[N-1]，則A[N-2]與A[N-1]交換。第一輪比較完成后，列表元素中最大的數(shù)“沉”到列表最后，而那些較小的數(shù)如同氣泡一樣上浮一個(gè)位置，顧名思義“冒泡法”排序。第2輪比較：從第一個(gè)元素開始，對(duì)列表中前N-1個(gè)元素（第N個(gè)元素，即A[N-1]已經(jīng)最大，無需參加排序）繼續(xù)兩兩大小比較，如果不滿足升序關(guān)系，則交換。第二輪比較完成后，列表元素中次大的數(shù)“沉”到最后，即A[N-2]為列表元素中次大的數(shù)。以此類推，進(jìn)行第N-1輪比較后，列表中所有元素均按遞增順序排好序。程序運(yùn)行結(jié)果如下：[2,3,8,50,64,71,76,80,86,97]【例5.25】冒泡排序算法的實(shí)現(xiàn)（bubbleSort.py）defbubbleSort(a):foriinrange(len(a)-1,-1,-1):#外循環(huán)forjinrange(i):#內(nèi)循環(huán)ifa[j]>a[j+1]:#大數(shù)往下沉a[j],a[j+1]=a[j+1],a[j]#print(a)#跟蹤調(diào)試defmain():a=[2,97,86,64,50,80,3,71,8,76]bubbleSort(a)print(a)if__name__=='__main__':main()選擇排序法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的選擇法的基本思想是：每次在若干無序數(shù)據(jù)中查找最小數(shù)，并放在無序數(shù)據(jù)中的首位。其算法如下：（1）從N個(gè)元素的列表中找最小值及其下標(biāo)，最小值與列表的第1個(gè)元素交換。（2）從列表的第2個(gè)元素開始的N-1個(gè)元素中再找最小值及其下標(biāo)，該最小值（即整個(gè)列表元素的次小值）與列表第2個(gè)元素交換。（3）以此類推，進(jìn)行第N-1輪選擇和交換后，列表中所有元素均按遞增順序排好序?！纠?.26】選擇排序算法的實(shí)現(xiàn)（selectionSort.py）defselectionSort(a):foriinrange(0,len(a)):#外循環(huán)（0~N-1）m=i#當(dāng)前位置下標(biāo)forjinrange(i+1,len(a)):#內(nèi)循環(huán)ifa[j]<a[m]:#查找最小值的位置m=ja[i],a[m]=a[m],a[i]#元素交換#print(a)#跟蹤調(diào)試defmain():a=[59,12,77,64,72,69,46,89,31,9]selectionSort(a)print(a)if__name__=='__main__':main()程序運(yùn)行結(jié)果如下：[9,12,31,46,59,64,69,72,77,89]插入排序法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的插入排序法的基本思想是：依次檢查列表中的每個(gè)元素，將其插入到其左側(cè)已經(jīng)排好序的列表中的適當(dāng)位置。其算法如下：（1）第2個(gè)元素與列表中其左側(cè)的第1個(gè)元素比較，如果A[0]>A[1]，則交換位置，結(jié)果左側(cè)2個(gè)元素排序完畢。（2）第3個(gè)元素依次與其左側(cè)的列表的元素比較，直至插入對(duì)應(yīng)的排序位置，結(jié)果左側(cè)的3個(gè)元素排序完畢。（3）以此類推，進(jìn)行第N-1輪比較和交換后，列表中所有元素均按遞增順序排好序?！纠?.27】插入排序算法的實(shí)現(xiàn)（insertSort.py）definsertSort(a):foriinrange(1,len(a)):#外循環(huán)（1~N-1）j=iwhile(j>0)and(a[j]<a[j-1]):#內(nèi)循環(huán)a[j],a[j-1]=a[j-1],a[j]#元素交換j-=1#繼續(xù)循環(huán)#print(a)#跟蹤調(diào)試defmain():a=[59,12,77,64,72,69,46,89,31,9]insertSort(a)print(a)if__name__=='__main__':main()程序運(yùn)行結(jié)果如下：[9,12,31,46,59,64,69,72,77,89]歸并排序法歸并排序法基于分而治之（DivideandConquer）的思想。算法的操作步驟如下。（1）將包含N個(gè)元素的列表分成兩個(gè)含N/2元素的子列表。（2）對(duì)兩個(gè)子列表遞歸調(diào)用歸并排序（最后可以將整個(gè)列表分解成N個(gè)子列表）。（3）合并兩個(gè)已排序好的子列表?！纠?.28】歸并排序算法的實(shí)現(xiàn)（mergeSort.py）defmerge(left,right):#合并兩個(gè)列表merged=[]i,j=0,0#i和j分別作為left和right的下標(biāo)left_len,right_len=len(left),len(right)#獲取左右子列表長度whilei<left_lenandj<right_len:#循環(huán)歸并左右子列表元素ifleft[i]<=right[j]:merged.append(left[i])#歸并左子列表元素i+=1else:merged.append(right[j])#歸并右子列表元素j+=1merged.extend(left[i:])#歸并左子列表剩余元素merged.extend(right[j:])#歸并右子列表剩余元素#print(left,right,merged)#跟蹤調(diào)試returnmerged#返回歸并好的列表【例5.28】歸并排序算法的實(shí)現(xiàn)（mergeSort.py）defmergeSort(a):#歸并排序iflen(a)<=1:#空或者只有1個(gè)元素，直接返回列表returnamid=len(a)//2#列表中間位置left=mergeSort(a[:mid])#歸并排序左子列表right=mergeSort(a[mid:])#歸并排序右子列表returnmerge(left,right)#合并排好序的左右兩個(gè)子列表defmain():a=[59,12,77,64,72,69,46,89,31,9]a1=mergeSort(a)print(a1)if__name__=='__main__':main()程序運(yùn)行結(jié)果如下：[9,12,31,46,59,64,69,72,77,89]快速排序法（1）設(shè)置兩個(gè)變量i和j，分別為列表首末元素的下標(biāo)，即i=0，j=N-1。（2）設(shè)置列表的第1個(gè)元素作為關(guān)鍵數(shù)據(jù)，即key=A[0]。（3）從j開始向前搜索，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換。（4）從i開始向后搜索，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換。（5）重復(fù)第（3）和（4）步，直到i=j?？焖倥判蚴菍?duì)冒泡排序的一種改進(jìn)，由C.A.R.Hoare在1962年提出。其基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要?。蝗缓筮f歸對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序。快速排序算法的一趟排序的操作步驟如下。defquickSort(a,low,high):#對(duì)列表a快速排序，列表下界為low，上界為highi=low#i等于列表下界j=high#j等于列表上界ifi>=j:#如果下界大于等于上界，返回結(jié)果列表areturnakey=a[i]#設(shè)置列表的第1個(gè)元素作為關(guān)鍵數(shù)據(jù)whilei<j:#循環(huán)直到i=jwhilei<janda[j]>=key:#j開始向前搜索，找到第一個(gè)小于key的值a[j]j=j-1a[i]=a[j]whilei<janda[i]<=key:#i開始向后搜索，找到第一個(gè)大于key的a[i]i=i+1a[j]=a[i]a[i]=key#a[i]等于關(guān)鍵數(shù)據(jù)quickSort(a,low,i-1)#遞歸調(diào)用快速排序算法（列表下界為low，上界為i-1）quickSort(a,j+1,high)#遞歸調(diào)用快速排序算法（列表下界為j+1，上界為high）defmain():a=[59,12,77,64,72,69,46,89,31,9]quickSort(a,0,len(a)-1)print(a)if__name__=='__main__':main()程序運(yùn)行結(jié)果如下：[9,12,31,46,59,64,69,72,77,89]▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍▍【例5.29】快速排序算法的實(shí)現(xiàn)（quickSort.py）5.11應(yīng)用舉例【例5.30】簡(jiǎn)易花名冊(cè)管理系統(tǒng)（name_list.py）（1）defmenu():#顯示菜單print("="*35)print(“簡(jiǎn)易花名冊(cè)程序")print("1.顯示名字")print("2.添加名字")print("3.刪除名字")print("4.修改名字")print("5.查詢名字")print("6.退出系統(tǒng)")print("="*35)names=[]

#創(chuàng)建存儲(chǔ)花名冊(cè)的列表對(duì)象whileTrue:

#重復(fù)執(zhí)行menu()

#顯示菜單num=input("請(qǐng)輸入選擇的功能序號(hào)（1到6)：")#獲取用戶輸入#根據(jù)用戶選擇，執(zhí)行相應(yīng)的功能ifnum=='1':print(names)elifnum=='2':name=input("請(qǐng)輸入要添加的名字：")names.append(name)print(names)elifnum=='3':name=input("請(qǐng)輸入要?jiǎng)h除的名字：")ifnameinnames:names.remove(name)基于列表的簡(jiǎn)易花名冊(cè)管理系統(tǒng)：通過列表可以很方便實(shí)現(xiàn)一個(gè)花名冊(cè)管理系統(tǒng)，實(shí)現(xiàn)名字的顯示、查詢、增加、刪除、修改等功能【例5.30】簡(jiǎn)易花名冊(cè)管理系統(tǒng)（name_list.py）（2）else:print("系統(tǒng)中不存在名字：{}".format(name))print(names)elifnum=='4':name=input("請(qǐng)輸