Personal nest in the information age

Python3实现冒泡排序和归并排序

示例代码:

#!/usr/bin/env python3
# -*- coding:UTF-8 -*-
import random
# 冒泡排序-升序
def bubble_sort(seq):
    seqLen=len(seq)
    for i in range(seqLen-1):
        for j in range(seqLen-i-1):
            if seq[j]>seq[j+1]:
                seq[j],seq[j+1]=seq[j+1],seq[j]
##########################################
# 归并排序(递归)-降序
def merge_sort(seq):
    if len(seq)<=1: # 列表长度小于等于1函数就结束
        return seq
    # mid将列表seq均分成两部分,左半部分记为left,右半部分记为right,递归划分left,right
    mid=len(seq)//2
    left,right = merge_sort(seq[:mid]),merge_sort(seq[mid:])
    return merge(left,right)
# 归并过程
def merge(left,right):
    result=[]   # 用于保存排序结果
    i=j=0   # 已排序的范围
    # 列表left和right从左往右两两元素比较,哪个大就把哪个追加到result列表
    leftLen,rightLen = len(left),len(right)
    while i<leftLen and j<rightLen:
        if left[i]>=right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
    # 如果两个分列表有一个已经比较结束,另一个列表剩下的部分直接全部放到result列表最后
    result+=left[i:]+right[j:]
    return result
if __name__ == '__main__':
    # 使用列表推导初始化list
    # 在[0,100)范围内随机抽取len(i)个数组成一个列表,随机生成len(i)范围:[1,20]
    li=[i for i in random.sample(range(100), random.randint(1,20))]
    print("排序前:%s\n"%li)
    # 冒泡排序的结果:
    listOfBubble=li.copy()  # 拷贝list给冒泡排序用
    bubble_sort(listOfBubble)
    print("冒泡排序升序后:%s"%listOfBubble)
    # 归并排序的结果:
    print("归并排序降序后:%s"%merge_sort(li))

示例输出:

排序前:[16, 47, 57, 39, 2, 81]
冒泡排序升序后:[2, 16, 39, 47, 57, 81]
归并排序降序后:[81, 57, 47, 39, 16, 2]

Bibliography

Leave a comment

Your email address will not be published. Required fields are marked *