的变化 )按字母顺序排序:Tim,Dot,Eva,Rom,Kim,gug,Amn,Jm,Kay,Ron,Jam (2)按数值递增顺序排序:26,33,35,29,19,12,22 (3)同样7个数字,换一个初始排列,再按数值的递增顺序排序:12,19,3326,29,35, 【解答】 9-15如果只想在一个有n个元素的任意序列中得到其中最小的第k(k<<m)个元素之前的部 分排序序列,那么最好采用什么排序方法?为什么?例如有这样一个序列:{503,017,512 908,170,897,275,653,612154,509,612*,677,765,094},要得到其第4个元素之前的部分 有序序列:{017,094,154,170},用所选择的算法实现时,要执行多少次比较? 【解答】 一般来讲,当n比较大且要选的数据k<<n时,采用堆排序方法中的筛选(调整)算法最 好。但当n比较小时,采用锦标赛排序方法更好。 例如,对于序列{57,40,38,11,13,34,4875,6,19,9,7},选最小的数据6,需形成初 始堆,进行18次数据比较:选次小数据7时,需进行4次数据比较:再选数据9时,需进 行6次数据比较;选数据11时,需进行4次数据比较 38 11133448形成初始堆 7540195738 但如果选用锦标赛排序,对于有n个数据的序列,选最小数据需进行n-1次数据比较 以后每选一个数据,进行数据比较的次数,均需Log2n次。例如,同样12个数据,第 次选最小的数据6,需进行次数据比较,以后选7、9、11时,都是Log212」=3次数据 比较。 9-16希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。 【解答】 (1)希尔排序{512275275*061}增量为2 275*061512275}增量为1 {061275*275512} (2)直接选择排序{275275*512061}i=1 061275*512275}i=2 061275*512275}i=3 {061275*275512} (3)快速排序{512275275*} 275*275512} (4)堆排序 275275*061170}已经是最大堆,交换275与170 5}对前3个调整 275*170061275}前3个最大堆,交换275*与06 061170275*275}对前2个调整 170061275*275}前2个最大堆,交换170与061的变化。 (1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22 (3) 同样 7 个数字，换一个初始排列，再按数值的递增 顺序排序：12, 19, 33, 26, 29, 35, 22 【解答】 9-15 如果只想在一个有 n 个元素的任意序列中得到其中最小的第 k (k<<n) 个元素之前的部 分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列: {503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094}, 要得到其第 4 个元素之前的部分 有序序列: {017, 094, 154, 170}, 用所选择的算法实现时, 要执行多少次比较? 【解答】 一般来讲，当 n 比较大且要选的数据 k << n 时, 采用堆排序方法中的筛选(调整)算法最 好。但当 n 比较小时，采用锦标赛排序方法更好。 例如，对于序列{ 57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7 }，选最小的数据 6，需形成初 始堆，进行 18 次数据比较；选次小数据 7 时，需进行 4 次数据比较；再选数据 9 时，需进 行 6 次数据比较；选数据 11 时，需进行 4 次数据比较。 但如果选用锦标赛排序，对于有 n 个数据的序列，选最小数据需进行 n -1 次数据比较， 以后每选一个数据，进行数据比较的次数，均需 log2n 次。例如，同样 12 个数据，第一 次选最小的数据 6，需进行 11 次数据比较，以后选 7、9、11 时，都是 log212 = 3 次数据 比较。 9-16 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。 【解答】 (1) 希尔排序 { 512 275 275* 061 } 增量为 2 { 275* 061 512 275 } 增量为 1 { 061 275* 275 512 } (2) 直接选择排序 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 } (3) 快速排序 { 512 275 275* } { 275* 275 512 } (4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换 275 与 170 { 170 275* 061 275 } 对前 3 个调整 { 275* 170 061 275 } 前 3 个最大堆，交换 275*与 061 { 061 170 275* 275 } 对前 2 个调整 { 170 061 275* 275 } 前 2 个最大堆，交换 170 与 061 { 061 170 275* 275 }