數(shù)據(jù)結(jié)構(gòu)作業(yè)題(參考版)
2025-03-28 03:01本頁面
【正文】 排序碼比較5次182016*2163028106126 1816* 20 1210 2816 302 12排序碼比較6次6 1810 16* 20 282 12 16 30排序碼比較7次排序碼比較9次2 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 28 30。設(shè)待排序的數(shù)據(jù)對象有n個。(5) 直接選擇排序初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 0[ 12 2 16 30 28 10 16* 20 618 ] 9 i = 1 2[ 12 16 30 28 10 16* 20 618 ] 8 i = 2 2 6 [ 16 30 28 10 16* 20 1218 ] 7 i = 3 2 6 10 [ 30 28 16 16* 20 1218 ] 6 i = 4 2 6 10 12[ 28 16 16* 20 3018 ] 5 i = 5 2 6 10 12 16[ 28 16* 20 3018 ] 4 i = 6 2 6 10 12 16 16*[ 28 20 3018 ] 3 i = 7 2 6 10 12 16 16* 18[ 20 3028 ] 2 i = 8 2 6 10 12 16 16* 16 20[ 3028 ] 1 2 6 10 12 16 16* 16 20 28[ 30 ] (6)基數(shù)排序 621630102816*201812按最低位分配r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9]62021816*1028163012f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]2862101816*16122030收集按最高位分配18r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9]16*16286f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]123020210302820181610126216*收集 (7) 堆排序第一步，形成初始的最大堆 (略)，第二步，做堆排序。需要注意，當a 1/2時，增量序列可能不以1結(jié)束，需要加以判斷和調(diào)整。大量實驗表明，取α=。αnα, 235。nα, 235。一般地，增量序列可采用235。/2n/2, 235。n/2, 235。 (1) 直接插入排序 (2) 希爾排序(增量為5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接選擇排序 (6) 基數(shù)排序 (7) 堆排序 (8) 二路歸并排序 【解答】(1) 直接插入排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 1[ 12 ] 21630281016*20 618 1 i = 2[ 212 ]1630281016*20 618 1 i = 3[ 212 16 ]30281016*20 618 1 i = 4[ 212 16 30 ]281016*20 618 2 i = 5[ 212 16 2830 ]1016*20 618 5 i = 6[ 21012162830 ]16*20 618 3 i = 7[ 210121616*2830 ]20 618 3 i = 8[ 210121616*202830 ] 618 3 i = 9[ 2 610121616*202830 ]18 8[ 2 610121616*18202830 ](2) 希爾排序(增量為5,2,1)初始排列 0 1 2 3 4 5 6 7 8 9排序碼比較次數(shù)
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1