对下列一组关键字 (46,58,15,45, 90,18,10,62,46,58',15',45,90',18',10',62°)口(1)写出所有的逆序对 口(2)写出直接插入排序过程 口(3)写出希尔排序过程(自选增量序列并说明选择的原因)□(4)写出快速排序过程(自选主元并说明选择的原因)口(5)写出归并排序过程
时间: 2023-08-20 14:04:02 浏览: 92
口(1)所有的逆序对为:(58,46), (58',46), (90',15'), (90',18'), (90',10'), (62',15'), (62',18'), (62',10'), (62',45'), (62',45), (90,15), (90,18), (90,10), (90,45), (18',15'), (18',10'), (45',15'), (45',18'), (45',10'), (45',46'), (45',46), (62,15), (62,18), (62,10), (62,45), (62',15), (62',18), (62',10), (62',45), (90,58), (90',58'), (18,15), (18,10), (45,15), (45,10), (45,46), (45',58'), (45,58)
口(2)直接插入排序过程:
首先将第一个元素 46 看做已经有序,从第二个元素 58 开始插入,因为 58 > 46,所以将 58 插入到 46 的后面得到 (46, 58)。然后将 15 插入到 (46, 58) 中,得到 (15, 46, 58)。以此类推,最终得到排序结果为 (10, 15, 18, 45, 46, 58, 62, 90)。
口(3)希尔排序过程:
选择增量序列为 {4, 2, 1},首先按照增量为 4 进行分组,得到 (46, 90, 18, 45)、(58, 10, 62, 15)、(15', 90', 18', 45')、(58', 10', 62', 46')。对每个分组内部进行插入排序,得到 (45, 18, 46, 90)、(15, 10, 62, 58)、(45', 18', 15', 90')、(46', 10', 58', 62')。然后按照增量为 2 进行分组,得到 (45, 46, 18, 90, 15, 62, 10, 58)、(45', 46', 18', 90', 15', 62', 10', 58')。对每个分组内部进行插入排序,得到 (10, 15, 18, 45, 46, 58, 62, 90)、(10', 15', 18', 45', 46', 58', 62', 90')。最终得到排序结果为 (10, 15, 18, 45, 46, 58, 62, 90)。
口(4)快速排序过程:
选择主元为中位数,首先以 46 为主元将序列分为两个部分:(45, 15, 10, 18, 46) 和 (58, 90, 62, 58', 90', 15', 18', 10', 62')。对每个部分分别进行快速排序,以 18 为主元将左侧部分分为 (15, 10, 18) 和 (45, 46),以 62 为主元将右侧部分分为 (58, 15', 18', 10', 62') 和 (90, 58', 90', 46')。继续对每个部分分别进行快速排序,以 15 为主元将左侧部分分为 (10, 15) 和 (18),以 18' 为主元将右侧部分分为 (15', 10', 18') 和 (58', 90', 62', 46', 90', 62')。继续对每个部分分别进行快速排序,以 10 为主元将左侧部分分为 (10) 和 (15),以 58' 为主元将右侧部分分为 (46', 58', 62') 和 (90', 62', 18')。最终得到排序结果为 (10, 15, 18, 45, 46, 58, 62, 90)。
口(5)归并排序过程:
首先将序列分为单个元素序列,然后两两合并,得到 (15, 45), (46, 58), (10, 18), (62, 90), (15', 18'), (10', 45'), (58', 62'), (46', 90')。然后将相邻的两个序列合并,得到 (15, 45, 46, 58), (10, 18, 62, 90), (15', 18', 10', 45'), (46', 58', 62', 90')。最后将相邻的两个序列合并,得到 (10, 15, 18, 45, 46, 58, 62, 90)。最终得到排序结果为 (10, 15, 18, 45, 46, 58, 62, 90)。