python - 与 Python 合并排序

Question

我找不到任何有效的 Python 3.3 合并排序算法代码，所以我自己做了一个。有什么办法可以加快速度吗？它在大约 0.3-0.5 秒内对 20,000 个数字进行排序

def msort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2)
    y = msort(x[:mid])
    z = msort(x[mid:])
    while (len(y) > 0) or (len(z) > 0):
        if len(y) > 0 and len(z) > 0:
            if y[0] > z[0]:
                result.append(z[0])
                z.pop(0)
            else:
                result.append(y[0])
                y.pop(0)
        elif len(z) > 0:
            for i in z:
                result.append(i)
                z.pop(0)
        else:
            for i in y:
                result.append(i)
                y.pop(0)
    return result

score 75 · Accepted Answer

第一个改进是简化主循环中的三种情况：不是在某些序列有元素时进行迭代，而是在两个序列都有元素时进行迭代。离开循环时，其中一个是空的，我们不知道哪个，但我们不在乎：我们将它们附加到结果的末尾。

def msort2(x):
    if len(x) < 2:
        return x
    result = []          # moved!
    mid = int(len(x) / 2)
    y = msort2(x[:mid])
    z = msort2(x[mid:])
    while (len(y) > 0) and (len(z) > 0):
        if y[0] > z[0]:
            result.append(z[0])
            z.pop(0)
        else:
            result.append(y[0])
            y.pop(0)
    result += y
    result += z
    return result

第二个优化是避免popping 元素。相反，有两个索引：

def msort3(x):
    if len(x) < 2:
        return x
    result = []
    mid = int(len(x) / 2)
    y = msort3(x[:mid])
    z = msort3(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

最后的改进在于使用非递归算法对短序列进行排序。在这种情况下，我使用内置sorted函数并在输入大小小于 20 时使用它：

def msort4(x):
    if len(x) < 20:
        return sorted(x)
    result = []
    mid = int(len(x) / 2)
    y = msort4(x[:mid])
    z = msort4(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

我对 100000 个整数的随机列表进行排序的测量结果是原始版本为 2.46 秒，msort2 为 2.33，msort3 为 0.60，msort4 为 0.40。作为参考，对所有列表进行排序sorted需要 0.03 秒。

score 28 · Accepted Answer

麻省理工学院课程的代码。（与通用合作者）

import operator


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


def mergeSort(L, compare=operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

score 21 · Accepted Answer

def merge_sort(x):

    if len(x) < 2:return x

    result,mid = [],int(len(x)/2)

    y = merge_sort(x[:mid])
    z = merge_sort(x[mid:])

    while (len(y) > 0) and (len(z) > 0):
            if y[0] > z[0]:result.append(z.pop(0))   
            else:result.append(y.pop(0))

    result.extend(y+z)
    return result

score 16 · Accepted Answer

您可以在对 mergesort 的顶级调用中初始化整个结果列表：

result = [0]*len(x)   # replace 0 with a suitable default element if necessary. 
                      # or just copy x (result = x[:])

然后对于递归调用，您可以使用一个辅助函数，您可以将其传递给的不是子列表，而是索引x。底层调用直接读取x和写入它们的值result。

这样你就可以避免所有应该提高性能的poping 和ing 。append

score 13 · Accepted Answer

拿我的实现

def merge_sort(sequence):
    """
    Sequence of numbers is taken as input, and is split into two halves, following which they are recursively sorted.
    """
    if len(sequence) < 2:
        return sequence

    mid = len(sequence) // 2     # note: 7//2 = 3, whereas 7/2 = 3.5

    left_sequence = merge_sort(sequence[:mid])
    right_sequence = merge_sort(sequence[mid:])

    return merge(left_sequence, right_sequence)

def merge(left, right):
    """
    Traverse both sorted sub-arrays (left and right), and populate the result array
    """
    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

# Print the sorted list.
print(merge_sort([5, 2, 6, 8, 5, 8, 1]))

score 7 · Accepted Answer

正如已经说过的，l.pop(0)是一个 O(len(l)) 操作并且必须避免，上面的 msort 函数是 O(n**2)。如果效率很重要，索引会更好，但也有成本。对于for x in lmergesort 来说更快但不容易实现：iter可以在这里使用。最后，检查i < len(l)两次，因为在访问元素时再次进行了测试：异常机制（尝试除外）更好，最后提高了 30% 。

def msort(l):
    if len(l)>1:
        t=len(l)//2
        it1=iter(msort(l[:t]));x1=next(it1)
        it2=iter(msort(l[t:]));x2=next(it2)
        l=[]
        try:
            while True:
                if x1<=x2: l.append(x1);x1=next(it1)
                else     : l.append(x2);x2=next(it2)
        except:
            if x1<=x2: l.append(x2);l.extend(it2)
            else:      l.append(x1);l.extend(it1)
    return l

score 6 · Accepted Answer

像这样的循环可能会被加速：

for i in z:
    result.append(i)
    z.pop(0)

相反，只需这样做：

result.extend(z)

请注意，无需清理的内容，z因为无论如何您都不会使用它。

score 5 · Accepted Answer

计算反转并遵守sorted界面的更长的。修改它以使其成为就地排序的对象的方法是微不足道的。

import operator

class MergeSorted:

    def __init__(self):
        self.inversions = 0

    def __call__(self, l, key=None, reverse=False):

        self.inversions = 0

        if key is None:
            self.key = lambda x: x
        else:
            self.key = key

        if reverse:
            self.compare = operator.gt
        else:
            self.compare = operator.lt

        dest = list(l)
        working = [0] * len(l)
        self.inversions = self._merge_sort(dest, working, 0, len(dest))
        return dest

    def _merge_sort(self, dest, working, low, high):
        if low < high - 1:
            mid = (low + high) // 2
            x = self._merge_sort(dest, working, low, mid)
            y = self._merge_sort(dest, working, mid, high)
            z = self._merge(dest, working, low, mid, high)
            return (x + y + z)
        else:
            return 0

    def _merge(self, dest, working, low, mid, high):
        i = 0
        j = 0
        inversions = 0

        while (low + i < mid) and (mid + j < high):
            if self.compare(self.key(dest[low + i]), self.key(dest[mid + j])):
                working[low + i + j] = dest[low + i]
                i += 1
            else:
                working[low + i + j] = dest[mid + j]
                inversions += (mid - (low + i))
                j += 1

        while low + i < mid:
            working[low + i + j] = dest[low + i]
            i += 1

        while mid + j < high:
            working[low + i + j] = dest[mid + j]
            j += 1

        for k in range(low, high):
            dest[k] = working[k]

        return inversions


msorted = MergeSorted()

用途

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l)
>>> s
[1, 2, 3, 4, 5]
>>> msorted.inversions
6

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key)
>>> s
['c', 'b', 'd', 'e', 'a']
>>> msorted.inversions
5

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l, reverse=True)
>>> s
[5, 4, 3, 2, 1]
>>> msorted.inversions
4

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key, reverse=True)
>>> s
['a', 'e', 'd', 'b', 'c']
>>> msorted.inversions
5

score 3 · Accepted Answer

这是CLRS实现：

def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    right, left = [], []
    for i in range(n1):
        left.append(arr[p + i])
    for j in range(n2):
        right.append(arr[q + j + 1])
    left.append(float('inf'))
    right.append(float('inf'))
    i = j = 0
    for k in range(p, r + 1):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1


def merge_sort(arr, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)


if __name__ == '__main__':
    test = [5, 2, 4, 7, 1, 3, 2, 6]
    merge_sort(test, 0, len(test) - 1)
    print test

结果：

[1, 2, 2, 3, 4, 5, 6, 7]

score 3 · Accepted Answer

许多人已经正确回答了这个问题，这只是另一种解决方案（尽管我的解决方案与 Max Montana 非常相似），但我在实现方面几乎没有区别：

在我们进入代码之前，让我们回顾一下这里的总体思路：

将列表分成大致相等的两半。
对左半部分进行排序。
对右半部分进行排序。
将两个排序的一半合并到一个排序列表中。

这是代码（用python 3.7测试）：

def merge(left,right):
    result=[] 
    i,j=0,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.extend(left[i:]) # since we want to add each element and not the object list
    result.extend(right[j:])
    return result

def merge_sort(data):
    if len(data)==1:
        return data
    middle=len(data)//2
    left_data=merge_sort(data[:middle])
    right_data=merge_sort(data[middle:])
    return merge(left_data,right_data)


data=[100,5,200,3,100,4,8,9] 
print(merge_sort(data))

score 2 · Accepted Answer

def merge(l1, l2, out=[]):
    if l1==[]: return out+l2
    if l2==[]: return out+l1
    if l1[0]<l2[0]: return merge(l1[1:], l2, out+l1[0:1])
    return merge(l1, l2[1:], out+l2[0:1])
def merge_sort(l): return (lambda h: l if h<1 else merge(merge_sort(l[:h]), merge_sort(l[h:])))(len(l)/2)
print(merge_sort([1,4,6,3,2,5,78,4,2,1,4,6,8]))

score 2 · Accepted Answer

这是另一个解决方案

class MergeSort(object):
    def _merge(self,left, right):
        nl = len(left)
        nr = len(right)
        result = [0]*(nl+nr)
        i=0
        j=0
        for k in range(len(result)):
            if nl>i and nr>j:
                if left[i] <= right[j]:
                    result[k]=left[i]
                    i+=1
                else:
                    result[k]=right[j]
                    j+=1
            elif nl==i:
                result[k] = right[j]
                j+=1
            else: #nr>j:
                result[k] = left[i]
                i+=1
        return result

    def sort(self,arr):
        n = len(arr)
        if n<=1:
            return arr 
        left = self.sort(arr[:n/2])
        right = self.sort(arr[n/2:] )
        return self._merge(left, right)
def main():
    import random
    a= range(100000)
    random.shuffle(a)
    mr_clss = MergeSort()
    result = mr_clss.sort(a)
    #print result

if __name__ == '__main__':
    main()

这是包含 100000 个元素的列表的运行时间：

real    0m1.073s
user    0m1.053s
sys         0m0.017s

score 2 · Accepted Answer

派对有点晚了，但我想我会把我的帽子扔进戒指，因为我的解决方案似乎比 OP 运行得更快（无论如何在我的机器上）：

# [Python 3]
def merge_sort(arr):
    if len(arr) < 2:
        return arr
    half = len(arr) // 2
    left = merge_sort(arr[:half])
    right = merge_sort(arr[half:])
    out = []
    li = ri = 0  # index of next element from left, right halves
    while True:
        if li >= len(left):  # left half is exhausted
            out.extend(right[ri:])
            break
        if ri >= len(right): # right half is exhausted
            out.extend(left[li:])
            break
        if left[li] < right[ri]:
            out.append(left[li])
            li += 1
        else:
            out.append(right[ri])
            ri += 1
    return out

这没有任何 slow pop()s，一旦一个半数组用完，它会立即将另一个半数组扩展到输出数组，而不是开始一个新的循环。

我知道它取决于机器，但对于 100,000 个随机元素（高于merge_sort()与 Python 内置sorted()）：

merge sort: 1.03605 seconds
Python sort: 0.045 seconds
Ratio merge / Python sort: 23.0229

score 2 · Accepted Answer

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

score 2 · Accepted Answer

很高兴有很多答案，我希望你发现这个答案清晰、简洁、快速。

谢谢

import math

def merge_array(ar1, ar2):
    c, i, j= [], 0, 0

    while i < len(ar1) and j < len(ar2):
        if  ar1[i] < ar2[j]:
            c.append(ar1[i])
            i+=1
        else:
            c.append(ar2[j])
            j+=1     
    return c + ar1[i:] + ar2[j:]

def mergesort(array):
    n = len(array)
    if n == 1:
        return array
    half_n =  math.floor(n/2)  
    ar1, ar2 = mergesort(array[:half_n]), mergesort(array[half_n:])
    return merge_array(ar1, ar2)

score 2 · Accepted Answer

def merge(x):
    if len(x) == 1:
        return x
    else:
        mid = int(len(x) / 2)
        l = merge(x[:mid])
        r = merge(x[mid:])
    i = j = 0
    result = []
    while i < len(l) and j < len(r):
        if l[i] < r[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(r[j])
            j += 1
    result += l[i:]
    result += r[j:]
    return result

score 2 · Accepted Answer

在实现了不同版本的解决方案之后，我终于在 CLRS 版本的基础上做出了权衡来实现这些目标。

目标

不使用 list.pop() 来迭代值
不创建用于保存结果的新列表，而是修改原始列表
不使用 float('inf') 作为标记值

def mergesort(A, p, r):
    if(p < r):
        q = (p+r)//2
        mergesort(A, p, q)
        mergesort(A, q+1, r)
        merge(A, p, q, r)

def merge(A, p, q, r):
    L = A[p:q+1]
    R = A[q+1:r+1]
    i = 0
    j = 0
    k = p
    while i < len(L) and j < len(R):
        if(L[i] < R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    if i < len(L):
        A[k:r+1] = L[i:]

if __name__ == "__main__":
    items = [6, 2, 9, 1, 7, 3, 4, 5, 8]
    mergesort(items, 0, len(items)-1)
    print items
    assert items == [1, 2, 3, 4, 5, 6, 7, 8, 9]

参考

[1] 书籍：CLRS

[2] https://github.com/gzc/CLRS/blob/master/C02-Getting-Started/exercise_code/merge-sort.py

score 1 · Accepted Answer

试试这个递归版本

def mergeList(l1,l2):
    l3=[]
    Tlen=len(l1)+len(l2)
    inf= float("inf")
    for i in range(Tlen):
        print   "l1= ",l1[0]," l2= ",l2[0]
        if l1[0]<=l2[0]:
            l3.append(l1[0])
            del l1[0]
            l1.append(inf)
        else:
            l3.append(l2[0])
            del l2[0]
            l2.append(inf)
    return l3

def main():
    l1=[2,10,7,6,8]
    print mergeSort(breaklist(l1))

def breaklist(rawlist):
    newlist=[]
    for atom in rawlist:
        print atom
        list_atom=[atom]
        newlist.append(list_atom)
    return newlist

def mergeSort(inputList):
    listlen=len(inputList)
    if listlen ==1:
        return inputList
    else:
        newlist=[]
        if listlen % 2==0:
            for i in range(listlen/2):
                newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
        else:
            for i in range((listlen+1)/2):
                if 2*i+1<listlen:
                    newlist.append(mergeList(inputList[2*i],inputList[2*i+1]))
                else:
                    newlist.append(inputList[2*i])
        return  mergeSort(newlist)

if __name__ == '__main__':
    main()

score 1 · Accepted Answer

    def merge(a,low,mid,high):
        l=a[low:mid+1]
        r=a[mid+1:high+1]
        #print(l,r)
        k=0;i=0;j=0;
        c=[0 for i in range(low,high+1)]
        while(i<len(l) and j<len(r)):
            if(l[i]<=r[j]):

                c[k]=(l[i])
                k+=1

                i+=1
            else:
                c[k]=(r[j])
                j+=1
                k+=1
        while(i<len(l)):
            c[k]=(l[i])
            k+=1
            i+=1

        while(j<len(r)):
            c[k]=(r[j])
            k+=1
            j+=1
        #print(c)  
        a[low:high+1]=c  

    def mergesort(a,low,high):
        if(high>low):
            mid=(low+high)//2


            mergesort(a,low,mid)
            mergesort(a,mid+1,high)
            merge(a,low,mid,high)

    a=[12,8,3,2,9,0]
    mergesort(a,0,len(a)-1)
    print(a)

score 1 · Accepted Answer

以下代码在最后弹出（足够有效）并在返回时进行就地排序。

def mergesort(lis):
    if len(lis) > 1:
        left, right = map(lambda l: list(reversed(mergesort(l))), (lis[::2], lis[1::2]))
        lis.clear()
        while left and right:
            lis.append(left.pop() if left[-1] < right[-1] else right.pop())
        lis.extend(left[::-1])
        lis.extend(right[::-1])
    return lis

score 1 · Accepted Answer

如果您像这样更改代码，它将起作用。

def merge_sort(arr):
    if len(arr) < 2:
        return arr[:]
    middle_of_arr = len(arr) / 2
    left = arr[0:middle_of_arr]
    right = arr[middle_of_arr:]
    left_side = merge_sort(left)
    right_side = merge_sort(right)
    return merge(left_side, right_side)

def merge(left_side, right_side):
    result = []
    while len(left_side) > 0 or len(right_side) > 0:
        if len(left_side) > 0 and len(right_side) > 0:
            if left_side[0] <= right_side[0]:
                result.append(left_side.pop(0))
            else:
                result.append(right_side.pop(0))
        elif len(left_side) > 0:
            result.append(left_side.pop(0))
        elif len(right_side) > 0:
            result.append(right_side.pop(0))
    return result

arr = [6, 5, 4, 3, 2, 1]
# print merge_sort(arr)
# [1, 2, 3, 4, 5, 6]

score 0 · Accepted Answer

#here is my answer using two function one for merge and another for divide and 
 #conquer 
l=int(input('enter range len'))      
c=list(range(l,0,-1))
print('list before sorting is',c)
def mergesort1(c,l,r):    
    i,j,k=0,0,0
    while (i<len(l))&(j<len(r)):
        if l[i]<r[j]:
            c[k]=l[i]
            i +=1            
        else:
            c[k]=r[j]
            j +=1
        k +=1
    while i<len(l):
        c[k]=l[i]
        i+=1
        k+=1
    while j<len(r):
        c[k]=r[j]
        j+=1
        k+=1
    return c   
def mergesort(c):
    if len(c)<2:
        return c
    else:
        l=c[0:(len(c)//2)]
        r=c[len(c)//2:len(c)]
        mergesort(l)
        mergesort(r)
    return    mergesort1(c,l,r)

score 0 · Accepted Answer

我建议利用 Python3 的协议，而不是在这里、那里和任何地方传递比较器。

此外，基于 Knuth 的 shuffle 的一组简单测试也是验证实现正确性的一个不错的主意：

from abc import abstractmethod
from collections import deque


from typing import Deque, Protocol, TypeVar, List


from random import randint


class Comparable(Protocol):
    """Protocol for annotating comparable types."""

    @abstractmethod
    def __lt__(self: 'T', x: 'T') -> bool:
        pass

    @abstractmethod
    def __gt__(self: 'T', x: 'T') -> bool:
        pass


T = TypeVar('T', bound=Comparable)


def _swap(items: List[T], i: int, j: int):
    tmp = items[i]
    items[i] = items[j]
    items[j] = tmp


def knuths_shuffle(items: List[T]):
    for i in range(len(items) - 1, 1, -1):
        j = randint(0, i)
        _swap(items, i, j)
    return items


def merge(items: List[T], low: int, mid: int, high: int):
    left_q = deque(items[low: mid])
    right_q = deque(items[mid: high])

    def put(q: Deque[T]):
        nonlocal low
        items[low] = q.popleft()
        low += 1

    while left_q and right_q:
        put(left_q if left_q[0] < right_q[0] else right_q)

    def put_all(q: Deque[T]):
        while q:
            put(q)

    put_all(left_q)
    put_all(right_q)

    return items


def mergesort(items: List[T], low: int, high: int):
    if high - low <= 1:
        return
    mid = (low + high) // 2
    mergesort(items, low, mid)
    mergesort(items, mid, high)
    merge(items, low, mid, high)


def sort(items: List[T]) -> List[T]:
    """
    >>> for i in range(100):
    ...     rand = knuths_shuffle(list(range(100)))
    ...     assert sorted(rand) == sort(rand)
    """
    mergesort(items, 0, len(items))
    return items

score 0 · Accepted Answer

def merge_sort(l):
    if len(l) == 1:
        if len(n)> 0:
            for i in range(len(n)):
                if n[i] > l[0]:
                    break
            else:
                i = i+1
            n.insert(i, l[0])
        else:
            n.append(l[0])
    else:
        p = len(l)//2
        a = l[:p]
        b = l[p:]
        merge_sort(a)
        merge_sort(b)

m = [3,5,2,4,1]
n = []
merge_sort(m)
print(n)

score 0 · Accepted Answer

from run_time import run_time
from random_arr import make_arr

def merge(arr1: list, arr2: list):
    temp = []
    x, y = 0, 0
    while len(arr1) and len(arr2):
        if arr1[0] < arr2[0]:
            temp.append(arr1[0])
            x += 1
            arr1 = arr1[x:]
        elif arr1[0] > arr2[0]:
            temp.append(arr2[0])
            y += 1
            arr2 = arr2[y:]
        else:
            temp.append(arr1[0])
            temp.append(arr2[0])
            x += 1
            y += 1
            arr1 = arr1[x:]
            arr2 = arr2[y:]

    if len(arr1) > 0:
        temp += arr1
    if len(arr2) > 0:
        temp += arr2
    return temp

@run_time
def merge_sort(arr: list):
    total = len(arr)
    step = 2
    while True:
        for i in range(0, total, step):
            arr[i:i + step] = merge(arr[i:i + step//2], arr[i + step//2:i + step])
        step *= 2
        if step > 2 * total:
            return arr

arr = make_arr(20000)
merge_sort(arr)
# run_time is 0.10300588607788086

score 0 · Accepted Answer

这是我对python中递归merge_sort函数的尝试。请注意，这是我的第一个 python 类，也是我第一次遇到这个问题，所以如果我的代码很粗糙，请多多包涵，但它可以工作。

def merge_sort(S):
    temp = []

    if len(S) < 2:
        return S

    split = len(S) // 2
    left = merge_sort(S[:split])
    right = merge_sort(S[split:])

    finale = temp + merge(left, right)

    return finale


def merge(left, right):

    holder = []

    while len(left) > 0 and len(right) > 0:

        if left[0] < right[0]:

            holder.append(left[0])
            del left[0]

        elif left[0] > right[0]:

            holder.append(right[0])
            del right[0]

    if len(left) > 0:

        holder.extend(left)

    elif len(right) > 0:

        holder.extend(right)

    return holder

score 0 · Accepted Answer

这与上面的“MIT”解决方案和其他几个解决方案非常相似，但通过传递对左右分区的引用而不是位置索引，并在 for 中使用范围，以更“Pythonic”的方式回答了这个问题使用切片符号循环填充排序数组：

def merge_sort(array):
    n = len(array)
    if n > 1:
        mid = n//2
        left = array[0:mid]
        right = array[mid:n]
        print(mid, left, right, array)
        merge_sort(left)
        merge_sort(right)
        merge(left, right, array)

def merge(left, right, array):
    array_length = len(array)
    right_length = len(right)
    left_length = len(left)
    left_index = right_index = 0
    for array_index in range(0, array_length):
        if right_index == right_length:
            array[array_index:array_length] = left[left_index:left_length]
            break
        elif left_index == left_length:
            array[array_index:array_length] = right[right_index:right_length]
            break
        elif left[left_index] <= right[right_index]:
                array[array_index] = left[left_index]
                left_index += 1
        else:
            array[array_index] = right[right_index]
            right_index += 1

array = [99,2,3,3,12,4,5]
arr_len = len(array)
merge_sort(array)
print(array)
assert len(array) == arr_len

该解决方案使用 Python 方便的运算符找到左右分区//，然后将左右和数组引用传递给合并函数，合并函数反过来重建原始数组。诀窍在于清理：当您到达左侧或右侧分区的末尾时，原始数组将填充另一个分区中剩余的任何内容。

score 0 · Accepted Answer

def splitArray(s):
    return s[:len(s)//2], s[len(s)//2:]

# the idea here is i+j should sum to n as you increment i and j, 
# but once out of bound, the next item of a or b is infinity 
# therefore, the comparison will always switch to the other array
def merge(a, b, n):
    result = [0] * n
    a = a + [float('inf')]
    b = b + [float('inf')]
    result = [0] * n
    i, j = 0, 0
    for k in range(0, n):
        if a[i] < b[j]:
            result[k] = a[i]
            i+=1
        else:
            result[k] = b[j]
            j+=1
    return result

def mergeSort(items):
    n = len(items)
    baseCase = []
    if n == 0:
        return baseCase
    if n == 1:
        baseCase.append(items[0])
        return baseCase
    if n == 2:
        if items[0] < items[1]:
            baseCase.append(items[0])
            baseCase.append(items[1])
            return baseCase
        else:
            baseCase.append(items[1])
            baseCase.append(items[0])
            return baseCase
    left, right = splitArray(items)
    sortedLeft = mergeSort(left)
    sortedRight = mergeSort(right)
    return merge(sortedLeft,sortedRight,n)

# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
    print ("%d" %arr[i]),

arr = mergeSort(arr)
print ("\n\nSorted array is")
for i in range(n):
    print ("%d" %arr[i]),

score 0 · Accepted Answer

首先划分数组，直到它的大小大于 1（这是基本条件）并通过递归函数来完成。
比较左右子数组值并将这些值放入数组中。

检查左右数组中剩余的任何项目...

def 合并排序（my_array）：

递归划分数组的基本条件...

 if len(my_array) > 1:
     middle = len(my_array) // 2
     left_array = my_array[:middle]
     right_array = my_array[middle:]

#递归函数 merge_sort(left_array) merge_sort(right_array)

     i = 0 # index of left array...
     j = 0 # index of right array...
     k = 0 # index of new array...

     # conquer the array and sorted like below condition

     while i < len(left_array) and j < len(right_array):
         if left_array[i] < right_array[j]:
             my_array[k] = left_array[i]
             i += 1
         else:
             my_array[k] = right_array[j]
             j += 1

         k += 1
     # checking any item remain in left sub array....
     while i < len(left_array):
         my_array[k] = left_array[i]
         i += 1
         j += 1
     # checking any item remain in right sub array....
     while j < len(right_array):
         my_array[k] = right_array[j]
         j += 1
         k += 1

my_array = [11, 31, 7, 41, 101, 56, 77, 2] print("输入数组：",my_array)

merge_sort(my_array) print("排序后的数组：",my_array)

score 0 · Accepted Answer

def merge(arr, p, q, r):
    left = arr[p:q + 1]
    right = arr[q + 1:r + 1]
    left.append(float('inf'))
    right.append(float('inf'))
    i = j = 0
    for k in range(p, r + 1):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1


def init_func(function):
    def wrapper(*args):
        a = []
        if len(args) == 1:
            a = args[0] + []
            function(a, 0, len(a) - 1)
        else:
            function(*args)
        return a

    return wrapper


@init_func
def merge_sort(arr, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)
if __name__ == "__main__":
    test = [5, 4, 3, 2, 1]
    print(merge_sort(test))

结果将是

[1, 2, 3, 4, 5]

python - 与 Python 合并排序

30 回答 30

目标

参考

递归划分数组的基本条件...

Related

Reference