首页 > 试题广场 >

插入与归并(25)

[编程题]插入与归并(25)

热度指数：8427 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确
的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩
下1个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入描述:

输入在第一行给出正整数N (<=100)；随后一行给出原始序列的N个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以
空格分隔。

输出描述:

首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试
的结果是唯一的。数字间以空格分隔，且行末不得有多余空格。

示例1

输入

10<br/>3 1 2 8 7 5 9 4 6 0<br/>1 2 3 7 8 5 9 4 6 0

输出

Insertion Sort<br/>1 2 3 5 7 8 9 4 6 0

算法知识视频讲解

Python

北风扬尘尘飞扬

迭代归并排序,自己使用步长1,2,4,8.....解决

# -*- coding : utf-8 -*-

def merge_sort(l,l2):
    i=2
    count=0
    while i<=len(l):
        result=[]
        for j in range(int(len(l)/i)):
            result+=merge(l[j*i:j*i+int(i/2)],l[j*i+int(i/2):j*i+i])
        result+=l[int(len(l)/i)*i:]
        l=result.copy()
        if result==l2:
            count=i*2
        if i==count:
            break
        i*=2
    return result
def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left
    result += right
    return result


_ = input()
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
# insert
insert = l1.copy()
merge_l = l1.copy()
insert_flag = False
count=0
for i in range(1, len(insert)):
    j = i - 1
    temp = insert[i]
    while j >= 0 and insert[j] > temp:
        insert[j + 1] = insert[j]
        j -= 1
    insert[j + 1] = temp
    if l2 == insert:
        insert_flag = True
        count=i+1
    if i==count:
        break

if insert_flag:
    print('Insertion Sort')
    print(' '.join([str(i) for i in insert]))
else:
    print('Merge Sort')
    merge = merge_sort(merge_l,l2)
    print(' '.join([str(i) for i in merge]))

发表于 2019-05-30 21:35:43 回复(0)

Python

qswhy

N = int(input())
original = [i for i in input().split()]
tmp = [i for i in input().split()]
def IsInsert(tmplist,b,c):
    a = []
    for i in tmplist:
        a.append(i)
    flagI = False
    for i in range(1,c):
        coverflag = 0
        if a == b:
            flagI = True
        for j in range(i,0,-1):
            if a[j] < a[j-1]:
                a[j-1],a[j] = a[j],a[j-1]
            else:
                if j == i:
                    coverflag = 1
                break
        if flagI and coverflag == 0:
            print('Insertion Sort')
            print(' '.join(a))
            break

def merge(left,right):
    l,r = 0,0
    result = []
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    else:
        result += list(left[l:])
        result += list(right[r:])
    return result

def IsMerge(tmplist,b,c):
    a = []
    for i in tmplist:
        a.append(i)
    step = 1
    flag2,flag3 = False,False
    OutList = []
    while True:
        if OutList == b:
            flag2 = True
        List = []
        OutList = []
        if not flag3:
            for i in range(0,c,step):
                List.append(a[i:i+step])
            for i in range(0,len(List),2):
                if i < len(List) - 1:
                    OutList += merge(List[i],List[i+1])
                else:
                    OutList += merge(List[i],[])
        if flag2:
            print('Merge Sort')
            print(' '.join(OutList))
            break
        if flag3:
            break
        else:
            step = step * 2
            a = OutList
        if step > c:
            flag3 = True

IsInsert(original,tmp,N)
IsMerge(original,tmp,N)

发表于 2019-03-08 08:55:27 回复(0)

Python

hi_小茶

在pat上测试测试点4提示格式错误，但是在牛客上就通过了，有没有知道pat上测试点4是检测的什么？

def get_list(list):
    my_list = []
    for i in list:
        i = int(i)
        my_list.append(i)
    return my_list

def get_insertion(fir_list, last_list, num):
    flag = 0
    #fir_list.append('-9999')
    for i in range(num):
        if last_list[i] > last_list[i + 1]:
            flag = i + 1
            break
        
    #fir_list.pop(-1)
    if fir_list[flag:] == last_list[flag:]:
        list = last_list[:flag + 1]
        list.sort()
        fir_list = list + last_list[flag + 1 :]
        return True, fir_list
    else:
        return False, []
        
def get_next_list(fir_list_1, num, k):
    
    i = 0 
    j = i + k + 1
    my_list = []
    while i <= num:
        list = []
        list = fir_list_1[i:j]
        list.sort()
            
        i = j 
        j = i + k + 1
        my_list += list
        #print(list)
    return my_list        


    
num = int(input())
fir_list, last_list = input(), input()
fir_list_1, last_list_1 = fir_list.split(), last_list.split()
fir_list_2, last_list_2 = fir_list.split(), last_list.split()


fir_list_1 = get_list(fir_list_1)
fir_list_2 = get_list(fir_list_2)
last_list_1 = get_list(last_list_1)
last_list_2 = get_list(last_list_2)

list = fir_list.split()
list = get_list(list)
list.sort()
if list == last_list_1:
    pass
else:
    flag, result_list = get_insertion(fir_list_1, last_list_1, num)
    if flag:
        print("Insertion Sort")
        for i in result_list:
            if i == result_list[-1]:
                print(i)
            else:
                print(str(i) + ' ', end = '')
    else:
        print("Merge Sort")
        flag = 0
        i = 0 
        while i < num:        
            k = 2 * i + 1
            list = get_next_list(fir_list_2, num, k)
            if list == last_list_2:
                i = k
                k = 2 * i + 1    
                list = get_next_list(fir_list_2, num, k)
                break
            i = k
        for i in list:
            if i == list[-1]:
                print(i)
            else:
                print(str(i) + ' ', end = '')

发表于 2017-11-23 21:02:11 回复(0)