35排序-資料下載頁(yè)
2025-08-23 15:08本頁(yè)面
【導(dǎo)讀】將記錄按關(guān)鍵字遞增(遞減)的次序排列起。來(lái),形成有序序列的過(guò)程,稱(chēng)為排序。內(nèi)排序是排序的基礎(chǔ)。比較次數(shù)來(lái)衡量。和無(wú)序兩個(gè)部分。{{a1}，{a2，a3，a4，…{{a1，a2}，{a3，a4…置,將該元素插入到有序數(shù)列的合適位置中。的位置將ai插入。3)重復(fù)2)，共進(jìn)行n-1的插入處理，數(shù)列全部。2)時(shí)間復(fù)雜度為O。列的最后（或最前）面，直到全部數(shù)列有序。1從原始數(shù)列{a1,a2,a3,…,an}，完成第1趟排序。說(shuō)明序列已有序，則停止交換。,An},選取中點(diǎn)元素K為分。序列元素均大于等于K值。行歸并操作，直到成為一個(gè)有序序列為止。4)將長(zhǎng)度為4的子序列合并為長(zhǎng)度為8的序列，
【正文】 18 23) 68 69) 70 (73 93) k = 90 13/16 歸并排序 ? 歸并排序法是將兩個(gè) （ 或兩個(gè)以上 ） 有序表合并成一個(gè)新的有序表；即把待排序序列分為若干個(gè)子序列 ， 每個(gè)子序列是有序的 。 然后再把有序子序列合并為整體有序序列 。 ? 若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為 2路歸并。 14/16 歸并排序算法 ? 1 把待排序的 n個(gè)記錄看作是長(zhǎng)度為 1的有序序列 。 將相鄰子序列兩兩歸并為長(zhǎng)度為 2的有序序列； ? 2 把得到的 n/2個(gè)長(zhǎng)度為 2的有序子序列再歸并為長(zhǎng)度為 2*2 的有序序列； ? 3 按 2 的方式 ， 重復(fù)對(duì)相鄰有序子序列進(jìn)行歸并操作 ， 直到成為一個(gè)有序序列為止 。 15/16 歸并排序算法簡(jiǎn)述 ? 待排序數(shù)列 {49,38,65,97,76,12,27}， ? 1)將每個(gè)元素看成是有序的子序列 : [49] [38] [65] [97] [76] [12] [27] ? 2)將長(zhǎng)度為 1的子序列合并為長(zhǎng)度為 2的子序列 : [38 ， 49] [65， 97] [12 ， 76] [ 27 ] ? 3)將長(zhǎng)度為 2的子序列合并為長(zhǎng)度為 4的子序列 : [38 ， 49 ， 65， 97] [12 ， 27， 76 ] ? 4)將長(zhǎng)度為 4的子序列合并為長(zhǎng)度為 8的序列，即 [12， 27， 38 ， 49 ， 65， 76， 97] 16/16 作業(yè)、思考題 第 3章作業(yè) 思考： 第 12題 作業(yè)：給定數(shù)列 {50 8 51 690 170、 89 27 65 426}，計(jì)算采用下列算法的比較次數(shù)： 插入、選擇、冒泡、快速、歸并排序。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1