[其它]ch10內(nèi)部排序-文庫(kù)吧資料
2024-10-22 17:39本頁面
【正文】 ] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 063 083 184 505 278 008 109 589 269 一趟收集： 50 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： 51 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： 52 ?算法描述 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ： ?分配 ： T(n)=O(n) ?收集 ： T(n)=O(rd) T(n)=O(d(n+rd)) 其中： n—— 記錄數(shù) d—— 關(guān)鍵字?jǐn)?shù) rd—— 關(guān)鍵字取值范圍 ? 空間復(fù)雜度 ： S(n)=2rd個(gè)隊(duì)列指針 53 一 .時(shí)間性能 1. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí) 2. 簡(jiǎn)單選擇排序 、 堆排序 和 歸并排序 的時(shí)間性能 不隨 記錄序列中關(guān)鍵字的分布而改變 。 29 選擇排序 簡(jiǎn)單選擇排序 ? 排序過程 ① 首先通過 n1次 關(guān)鍵字比較，從 n個(gè)記錄中找出關(guān)鍵字 最小 的記錄，將它與第一個(gè)記錄交換 ② 再通過 n2次 比較，從剩余的 n1個(gè)記錄中找出 關(guān)鍵字次小 的記錄，將它與第二個(gè)記錄交換 ③ 重復(fù)上述操作，共進(jìn)行 n1趟 排序后，排序結(jié)束 30 例 初始： [ 49 38 65 97 76 13 27 ] k j j j j j j k k i=1 13 49 一趟： 13 [38 65 97 76 49 27 ] i=2 k k j j j j j 27 38 二趟： 13 27 [65 97 76 49 38 ] 三趟： 13 27 38 [97 76 49 65 ] 四趟： 13 27 38 49 [76 97 65 ] 五趟： 13 27 38 49 65 [97 76 ] 六趟： 13 27 38 49 65 76 [97 ] 排序結(jié)束： 13 27 38 49 65 76 97 31 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ?記錄 移動(dòng)次數(shù) ?最好情況： 0 ?最壞情況： 3(n1) ?比較次數(shù) ： )(21)( 211nninni??????? 空間復(fù)雜度 ： S(n)=O(1) T(n)=O(n178。由于其排序速度快，因此稱快速排序 (quick sort)。 ：對(duì)于初始狀態(tài)如下的各個(gè)序列 （ 長(zhǎng)度為 n） 進(jìn)行直接插入排序時(shí) ， 至多需要進(jìn)行多少次關(guān)鍵字間的比較 （ 要求按照正序排序 ） ？ (1)關(guān)鍵字按照升序有序； (2)關(guān)鍵字按照逆序有序； (1)n1； (2)(n+2)(n1)/2； 22 交換排序 ?冒泡排序 ?排序過程 ? 將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序 r[1].keyr[2].key， 則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第 n1個(gè)記錄和第 n個(gè)記錄比較為止 —— 第一趟冒泡排序 ，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上 ? 對(duì)前 n1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第 n1個(gè)記錄位置 ? 重復(fù)上述過程，直到“ 在一趟排序過程中沒有進(jìn)行過交換記錄的操作 ”為止 23 例 49 38 65 97 76 13 27 30 初始關(guān)鍵字 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27 30 38 第五趟 38 49 76 97 1397 2797 3097 13 76 76 76 27 3013 65 2765 3065 13 13 49 49 3049 2738 27 38 30 38 1 2 3 4 5 6 7 8 24 ?算法描述 ?算法評(píng)價(jià) ? 時(shí)間復(fù)雜度 ?最好情況（正序） ?比較次數(shù)： n1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1