-1

我特别怀疑我对两种情况的合并排序的实现：

1. 如果列表的大小是 2，那么如果它们不是按升序排列的值，我已经交换了值，否则我已经返回它们。

2. 在合并功能中，当列表试图检查其中的元素数量时，我分配了最大的数字（9999），这样在与它比较的情况下总是错误的。
谁能告诉我合并排序的实现是否正确？就像排序完成一样，但是归并排序的实现是准确的还是由于情况而出错？

这是我的代码： 

# unsorted LIST
u_list = [3, 6, 8, 1, 4, 7, 2, 12, 45];

# Size of the unsorted list
global_size = len(u_list)

def foo(temp_list):
    size_of_list = len(temp_list)
    # If the size of the list is 1
    if size_of_list == 1:
        return temp_list

    # If the size of the list is 2
    if size_of_list == 2:
        if temp_list[0] > temp_list[1]:
            temp_list[0],temp_list[1] = temp_list[1],temp_list[0]
            return temp_list
        else: 
            return temp_list

    # If the size of the list is greater than 2                
    if size_of_list > 2:
        count = 1
        i = 0
        if size_of_list % 2 == 0:
            mid1 = size_of_list / 2
        else:
            mid1 = (size_of_list / 2) + 1

        mid2 = size_of_list - mid1

        newlist1 = list()
        newlist2 = list()

        for e in temp_list:
            if count >= mid1 + 1:
                newlist2.append(e)
            else:
                newlist1.append(e)
            if count == size_of_list:
                break
            count = count + 1
        sorted_list = list()
        return merge(foo(newlist1), foo(newlist2))

# Merging all the sorted components
def merge(list1, list2):
    i = 0
    j = 0
    k = 0
    size_of_list = len(list1) + len(list2)
    sorted_list = list()
    while k <= size_of_list - 1:
        if i == len(list1):
            list1.append(9999)
        if j == len(list2):
            list2.append(9999)

        if list1[i] < list2[j]:
            sorted_list.append(list1[i])
            i = i + 1
        elif list2[j] < list1[i]:
            sorted_list.append(list2[j])
            j = j + 1
        k = k + 1
    return sorted_list

print foo(u_list)
4

3 回答 3

19

老实说，看到这样的代码，我感到很不安；）。这可能是正确的，但我的直觉认为它不是（如果数字 > 9999 怎么办？）。它比必要的复杂。语法是 Python，但您没有使用 Python 的强大功能。

以下是我将如何在 Python 中实现合并排序：

def merge_sort(sequence):
    if len(sequence) < 2: 
        return sequence

    mid = int(len(sequence) / 2)
    left_sequence = merge_sort(sequence[:mid])
    right_sequence = merge_sort(sequence[mid:])
    return merge(left_sequence, right_sequence)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1 
    result += left[i:]
    result += right[j:]

    return result
于 2012-06-20T05:09:33.963 回答
2

不是最干净的代码，但它将通过合并排序方法完成工作。

方法一：

def merge_sorted(list1,list2):

    sorted = []

    i = 0

    k = 0

    while True:
        if i >= len(list1):                                                     
            sorted.extend(list2[k:])
            return sorted

        if k >= len(list2):
            sorted.extend(list1[i:])                                   
            return sorted

        if list1[i] <= list2[k]:
            sorted.append(list1[i])
            i += 1
        else:
            sorted.append(list2[k])
            k += 1

方法二：

def sort_method2(list0):

    unsorted_list = list0[:]

    if (len(unsorted_list) == 1 or len(unsorted_list) == 0): 

        return(unsorted_list)

    elif(len(unsorted_list) == 2): 

        if (unsorted_list[0] > unsorted_list[1]):

            temp = unsorted_list[0]

            unsorted_list[0] = unsorted_list[1]

            unsorted_list[1] = temp

        return(unsorted_list)
    else:
        length = len(unsorted_list)//2   

        first_list = sort_method2(unsorted_list[length:])   

        second_list = sort_method2(unsorted_list[:length]) 

        return(merge_sorted(first_list,second_list))

list3 = [8,8,2,63,2,6,3,4,2,6,2,6,8,5,4,3,6,-1,21,0,1,23,623,4, 0.001,5,4,256,4,0]

sort_method2(list3)

于 2013-04-12T20:58:57.423 回答
0

递归版本：将值从 sorted_lists 中删除后，将其推送到 merge_list 中，这是使用 pop() 完成的。

"""
This function merges two sorted arrays using recursion( sorted from left to right)
e.g
a = [1,2,3,4] and b = [5,6,7,8]
lets represent them like they are stacks and the smallest values can be popped out
so we send reversed lists into the function

_merge_two_sorted_lists(a[::-1], b[::-1])

"""
def _merge_two_sorted_lists(a1_L, b1_L, merged_sorted_lists = None):
    if merged_sorted_lists is None:
        merged_sorted_lists = []
    if not a1_L and not b1_L:
        return merged_sorted_lists

    if a1_L and b1_L:
        if a1_L[-1] < b1_L[-1]:
            merged_sorted_lists.append(a1_L.pop())
        else:
            merged_sorted_lists.append(b1_L.pop())
    elif a1_L and not b1_L:
        merged_sorted_lists.append(a1_L.pop())
    elif not a1_L and b1_L:
        merged_sorted_lists.append(b1_L.pop())

    return _merge_two_sorted_lists(a1_L, b1_L, merged_sorted_lists)
>>> a = [1, 2, 3]
>>> b = [3,4]
>>> _merge_two_sorted_lists(a[::-1],b[::-1])
>>> [1, 2, 3, 3, 4]
于 2019-12-08T04:23:30.143 回答