python - Python Merge Sort Recursive

python - Python Merge Sort Recursive,第1张

我遇到有关merge_sort函数的问题,特别是对正确的子列表执行递归排序。

为此作业提供的提示是:

# if min_ < max_
# calculate mid ((min   max) // 2)
#recursively sort left sub-list
# recursively sort right sub-list
# merge sorted sub-lists

# merge_sort function
"""
:param unsorted_list: The list to be sorted
:param min_: The minimum index to sort from the given list
:param max_: The maximum index to sort from the given list
Returns nothing, the original list is modified so no copy is needed
"""

Merge_sort函数

def merge_sort(unsorted_list, min_, max_):
    mid_ = (min_   max_) // 2
    if min_ < max_:
        merge_sort(unsorted_list, min_, mid_)
        merge(unsorted_list, min_, mid_)
        return merge_sort(unsorted_list, mid_   1, max_)
    merge(unsorted_list, mid_   1, max_)

test_list = [4, 12, 20, 1, 2, 17, 3, 11, 18, 1]

merge_sort(test_list, 0, len(test_list) - 1)

使用上面的测试列表测试我的函数会产生:

[1, 2, 4, 12, 20, 17, 3, 11, 18, 1]

表示左子列表正在工作但不是正确的子列表。

应该返回预期的输出:

[1, 1, 2, 3, 4, 11, 12, 17, 18, 20]

我的合并功能代码:

def merge(unsorted_list, min_, max_):
    # mid position = start of second sub-list
    mid = ((min_   max_) // 2)   1

    position1 = min_
    position2 = mid
    position3 = 0

    temp = []
    stop = False
    while stop == False and position2 < len(unsorted_list) and position1 < mid:
        if unsorted_list[position1] <= unsorted_list[position2]:
            temp.append(unsorted_list[position1])
            position1  = 1
            position3  = 1
        else:
            temp.append(unsorted_list[position2])
            position2  = 1
            position3  = 1

        if position1 >= position2:
            for k in range(position1, mid   1):
                temp.append(unsorted_list[k])
                position2  = 1
                position3  = 1
            stop = True
            if position3 == len(unsorted_list):# temp
                for i in range(len(temp)):
                    unsorted_list[min_] = temp[i]
                    min_  = 1
        elif position2 > max_:
            for k in range(position1, mid):
                temp.append(unsorted_list[k])
                position3  = 1
            stop = True
            if position3 == len(unsorted_list):# temp
                for i in range(len(temp)):
                    unsorted_list[min_] = temp[i]
                    min_  = 1

    if position3 != len(unsorted_list):
        for k in range(position2, len(unsorted_list)):
                temp.append(unsorted_list[k])
                position3  = 1
        if position3 > max_ and position3 == len(temp):
            for i in range(len(temp)):
                unsorted_list[min_] = temp[i]
                min_  = 1

最佳答案:

0 个答案:

没有答案
本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复