【正文】 然后將記錄從一個(gè)位置 移動(dòng) 到另一個(gè)位置。 第 96頁 排序方法 插入排序 選擇排序 交換排序 歸并排序 簡(jiǎn)單插入排序 希爾排序 簡(jiǎn)單選擇排序 堆排序 起泡排序 快速排序 第 97頁 插入排序 簡(jiǎn)單插入、希爾排序 簡(jiǎn)單插入排序 : ? 基本思想： 從數(shù)組的第 2號(hào)元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。 第 98頁 該算法適合于 n 較小的情況 ， 時(shí)間復(fù)雜度為 O(n2). 待排元素序列： [53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序： [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例 對(duì)于有 n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行 n1趟 最壞情況下： 需要 n(n1)/2次比較 最好： n1次比較 第 99頁 希爾排序： 希爾排序的基本思想 : 先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行 直接插入排序 ,待整個(gè)序列中的記錄“基本有序”時(shí) ,再對(duì)全 體記錄進(jìn)行一次直接插入排序 . 最壞情況下：需要 O( )次比較 第 100頁 簡(jiǎn)單選擇排序 ? 思想：首先從 1~n個(gè)元素中選出關(guān)鍵字 最小 的記錄交換到 第一個(gè) 位置上。然后再?gòu)牡?2 個(gè)到第 n個(gè)元素中選出次小的記錄交換到 第二個(gè) 位置上，依次類推。 選擇排序 簡(jiǎn)單選擇排序、堆排序 簡(jiǎn)單選擇排序法 , 最壞情況需要 n(n1)/2次比較； 時(shí)間復(fù)雜度為 O(n2)， 適用于 待排序元素較少 的情況。 第 101|92頁 ? 初態(tài)： [15， 14， 22， 30， 37， 15， 11] ? 第一趟： [11] [14， 22， 30， 37， 15， 15] ? 第二趟： [11， 14] [22， 30， 37， 15， 15] ? 第三趟： [11， 14， 15] [30， 37， 22， 15] ? 第四趟： [11， 14， 15， 15] [37， 22， 30] ? 第五趟： [11， 14， 15， 15， 22] [37， 30] ? 第六趟： [11， 14， 15， 15， 22， 30] [37] 有序序列 例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（ 15， 14， 22， 30，37， 11），每一趟排序后的序列狀態(tài)如圖所示 ： 第 102頁 堆排序 （ 也是一種選擇排序 ） 堆是具有特定條件的順序存儲(chǔ)的完全二叉樹 ， 其特定條件是： 任何一個(gè)非葉子結(jié)點(diǎn)的關(guān)鍵字大于等于 （ 或小于等于 ）子女的關(guān)鍵字的值 。 89 76 24 33 15 10 11 25 36 49 78 56 (a):堆頂元素取最大值 (b):堆頂元素取最小值 堆排序需要比較的次數(shù)為 O(nlog2n) (1) 堆的示例 第 103頁 交 換 排 序 交換排序的特點(diǎn)在于 交換 。有冒泡和快速排序兩種。 冒泡排序（起泡排序） 思想： 小的浮起 ， 大的沉底 。 從左端開始比較 。 第一趟：第 1個(gè)與第 2個(gè)比較 ， 大則交換；第 2個(gè)與第 3個(gè)比較 ， 大則交換 ， …… 關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對(duì)前 n1個(gè)記錄進(jìn)行同樣的操作 ， 關(guān)鍵字次大的記錄交換 到第 n1個(gè) 位置上； 依次類推 ， 則完成排序 。 第 104頁 冒泡排序 ? 冒泡排序的方法： ? 掃描整個(gè)線性表，逐次對(duì)相鄰的兩個(gè)元素進(jìn)行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大 (或最小 )的元素排到表的最后 (或最前 ) ； ? 除最后 (或最前 )一個(gè)元素，對(duì)剩余的元素重復(fù)上述過程，將次大 (或次小 )的數(shù)排到表的倒數(shù) (或正數(shù) )第二個(gè)位置； ? 重復(fù)上述過程； ? 對(duì)于長(zhǎng)度為 n的線性表，冒泡排序需要對(duì)表掃描 n1遍。 第 105頁 冒泡排序的方法 ?設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（ 18， 20， 15， 32， 4， 25），第一趟 冒泡排序后的序列狀態(tài)如圖所示 ： ? 18 20 15 32 4 25 ? 18 20 15 32 4 25 ? 18 15 20 32 4 25 ? 18 15 20 32 4 25 ? 18 15 20 4 32 25 ? 18 15 20 4 25 32 最大數(shù) ?第二趟冒泡排序 第 106頁 Q：第二趟冒泡排序后的結(jié)果是什么樣的？達(dá)到了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？ Q：你覺得冒泡排序的效率如何？如果是你，你會(huì)用什么方法來排序？ 冒泡排序比較簡(jiǎn)單，當(dāng)初始序列基本有序時(shí)，冒泡排序有較高的效率，反之效率較低。 ?冒泡排序終止條件 : 本趟排序未發(fā)生交換，終止排序算法 第 107頁 初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54 設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為（ 26,18,32,54,47,9,15 ) 冒泡排序法，需要比較的次數(shù)為 n(n1)/2； 第 108頁 快速排序 (對(duì)冒泡排序的改進(jìn)） 思想：通過一趟排序?qū)⒋判蛄?分成兩部分 ，使其中 一部分記錄 的關(guān)鍵字均比 另一部分小 ，再分別對(duì)這兩部分排序，以達(dá)到整個(gè)序列有序。 時(shí)間復(fù)雜度： O(log2n) 當(dāng)待排序列逆序時(shí) ， 蛻變成冒泡排序 ， 時(shí)間復(fù)雜度 : O(n(n1)/2) 第 109頁 內(nèi)部排序方法的選擇 各種排序方法各有優(yōu)缺點(diǎn)，故在不同情況下可作不同的選擇。通常需考慮的因素有 ：待排序的記錄個(gè)數(shù)；記錄本身的大小；記錄的鍵值分布情況 等。 ? 若待排序的記錄個(gè)數(shù) n較小時(shí)，可采用簡(jiǎn)單排序方法。 ? 若 n 較大時(shí)，應(yīng)采用快速排序或堆排序。 ? 若待排序的記錄已基本有序，可采用簡(jiǎn)單插入和起泡 排序。 第 110頁 方法 歸并排序 簡(jiǎn)單插入 希爾排序 簡(jiǎn)單選擇 堆排序 起泡排序 快速排序 插入 選擇 交換 比較次數(shù) 使用建議 查找 : 方法 順序 折半 比較次數(shù) log2n 最好 :1 最壞 :n 平均 :(n+1)/2 使用條件 順序存儲(chǔ)結(jié)構(gòu)的 有序表 任何表 排序 : n1 n(n1)/2 n(n1)/2 nlog2n n1 n(n1)/2 log2n n(n1)/2 正序的表、 n小的表 與表的初始數(shù)據(jù)無關(guān)、 n小的表 正序的表、 n小的表 n大的表 ,但逆序的表會(huì)蛻變?yōu)槠鹋菖判? 借助輔助空間最多的方法 n大的表 第 111|92頁 排序法小結(jié)： ?簡(jiǎn)單選擇排序法 , 最壞情況需要 n(n1)/2次比較； ?冒泡排序法 , 最壞情況需要 n(n1)/2次比較； ?希爾排序法 , 最壞情況需要 O()次比較； ?堆排序法 , 最壞情況需要 O(nlog2n)次比較； 第 112|92頁 排序查找方面的考題： (1) 對(duì)于長(zhǎng)度為 n的線性表 ， 在最壞情況下 ， 下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是 （ 2022年 4月 ） A) 冒泡排序?yàn)?n/2 B) 冒泡排序?yàn)?n C) 快速排序?yàn)?n D) 快速排序?yàn)?n(n1)/2 (2)在長(zhǎng)為 64的有序線性表中進(jìn)行順序查找 ， 最壞情況下需要比較的次數(shù)為 ______。（ 06年 9月 ） A） 63 B） 64 C） 6 D） 7 (3) 下列數(shù)據(jù)結(jié)構(gòu)中 ， 能用二分法進(jìn)行查找的是 （ 2022年 9月 ） A） 順序存儲(chǔ)的有序線性表 B） 線性鏈表 C） 二叉鏈表 D） 有序線性鏈表 (4) 下列排序方法中 ， 最壞情況下比較次數(shù)最少的是 （ 09年 3月 ） A） 冒泡排序 B） 簡(jiǎn)單選擇排序 C） 直接插入排序 D） 堆排序 D B A D 第 113頁 ?在長(zhǎng)度為 n的有序線性表中進(jìn)行二分查找。最壞的情況下，需要的比較次數(shù)為 【 2】 。 ?長(zhǎng)度為 n的順序存儲(chǔ)線性表中，當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為 【 1】 。 ?假設(shè)線性表的長(zhǎng)度為 n，則在最壞情況下，冒泡排序需要的比較次數(shù)為 A) log2n B) n2 C) O(n1..5) D) n(n1)/2 ?已知數(shù)據(jù)表 A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是 A) 堆排序 B) 直接插入排序 C) 快速排序 D) 直接選擇排序 例題講解 log2n n/2 第 114頁 ? 冒泡排序算法在最好的情況下的元素交換次數(shù)為 【 1】 。 ?在最壞情況下，堆排序需要比較的次數(shù)為 【 2】 。 ?最簡(jiǎn)單的交換排序方法是 A) 快速排序 B) 選擇排序 C) 堆排序 D) 冒泡排序 ?排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，常見的排序方法有插入排序、 【 1】 和選擇排序等。 0 nlog2n交換排序 第 115頁 ?在下列幾種排序方法中，要求內(nèi)存量最大的是 A) 插入排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序 ?希爾排序?qū)儆? A) 交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序 ?對(duì)長(zhǎng)度為 n的線性表進(jìn)行順序查找，在最壞的情況下所需要的比較次數(shù)為 Ａ ) n+1 B) n C) (n+1)/2 D) n/2 第 116頁 第 117頁 第二章 程序設(shè)計(jì)基礎(chǔ) 內(nèi)容： 1. 程序設(shè)計(jì)方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計(jì)。 3. 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象方法，屬性及繼承與多態(tài)性。 第 118頁 1. 源程序的文檔化 ? 符號(hào)的命名 :見名知意 ? 注釋（序言性和功能性注釋） ? 程序的視覺組織 :空格、空行、縮進(jìn)。 2. 數(shù)據(jù)說明 ? 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 ? 變量安排有序化 ? 對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明 3. 語句的結(jié)構(gòu) ? 每條語句簡(jiǎn)單明了 ?