Python-归并排序-Python在线学习

文章目录 [ 隐藏 ]

归并排序算法思路
算法实现

归并排序算法思路

归并排序主要思想是分治法(divide and conquer)，就是要将n个元素的序列划分为两个序列，再将两个序列划分为4个序列，
直到每个序列只有一个元素，最后，再将两个有序序列归并成一个有序的序列。

两个序列要归并成一个有序的序列，我们每次从两个列表开头元素选取较小的一个，直到某一个列表到达底部，再将另一个剩下部分顺序取出。添加到第一个队列后面

算法实现

# Filename : lean001.py
# author by : www.py40.com
#python归并排序算法
def mergeSort(seq):  
    if len(seq)<=1:  
        return seq  
    mid=int(len(seq)/2)  
    left=mergesort(seq[:mid])  
    right=mergesort(seq[mid:])  
    return merge(left,right)  
  
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+=left[i:]  
    result+=right[j:]  
    return result  
  
a = [1,15,12,3,56,42,1,44,32,25,6,7,32]
a = mergeSort(a)
print("result:"+str(a))

# Filename : lean001.py

# author by : www.py40.com

#python归并排序算法

def mergeSort(seq):

if len(seq)<=1:

return seq

mid=int(len(seq)/2)

left=mergesort(seq[:mid])

right=mergesort(seq[mid:])

return merge(left,right)

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+=left[i:]

result+=right[j:]

return result

a = [1,15,12,3,56,42,1,44,32,25,6,7,32]

a = mergeSort(a)

print("result:"+str(a))

运行结果

C:\Users\Administrator>E:\python\learn\lean001.py
result:[1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56]

1 2	C:\Users\Administrator>E:\python\learn\lean001.py result:[1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56]

未经允许不得转载：Python在线学习 » Python-归并排序

Python-归并排序

归并排序算法思路

算法实现

猜你喜欢

来吐槽吧 0