蓝桥杯备考冲刺必刷题(Python) | 3226 宝藏排序II

学习Python从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（Python） | 汇总-CSDN博客

【题目描述】

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

【输入】

输入第一行包括一个数字n，表示宝藏总共有n个。

输入的第二行包括n个数字， 第i个数字a[i]表示第i个宝藏的珍贵程度。

数据保证1≤n≤10^5，1≤a[i]≤10^9。

【输出】

输出n个数字，为对宝藏按照珍贵程度从小到大排序后的数组。

【输入样例】

5
1 5 9 3 7

【输出样例】

1 3 5 7 9

【代码详解】

# 使用快速排序编写（与学而思教的l,r指针不一样）
n = int(input())  # 输入n
a = [int(i) for i in input().split()]  # 输入a列表

def partition(a, left, right):  # 找到mid值，并将mid左边放比mid小的，mid右边放比mid大的
    idx = left+1  # 定义要交换的下标
    for i in range(left+1, right+1):  # 从left+1遍历至right
        if a[i]<=a[left]:  # 如果比基准值a[left]要小
            a[i],a[idx] = a[idx],a[i]  # 与要交换的下标进行交换
            idx+=1  # idx自增1
    a[left],a[idx-1] = a[idx-1],a[left]  # 最后将基准值与idx-1进行交换
    return idx-1  # 返回idx-1，其为mid

def quick_sort(a, left, right):  # 递归搜索
    if left<right:  # 保证left小于right，否则就是1个数的情况
        mid = partition(a, left, right)  # 获得mid值
        quick_sort(a, left, mid-1)  # 将mid左半边继续递归排序
        quick_sort(a, mid+1, right)  # 将mid右半边继续递归排序

quick_sort(a, 0, n-1)  # 调用快排
for i in range(len(a)):  # 输入排序后的a列表
    print(a[i], end=" ")

# 使用归并排序编写
n = int(input())  # 输入n
a = [int(i) for i in input().split()]  # 输入a列表

def Merge(A, B):
    result = []  # 定义个空列表保存结果
    while len(A)!=0 and len(B)!=0:  # 当A列表与B列表同时不为空时
        if A[0]<=B[0]:  # 进行首元素比较，较小的添加到result列表中，并弹出
            result.append(A.pop(0))
        else:
            result.append(B.pop(0))
    result.extend(A)  # 最后将剩余的A列表和B列表追加到result中
    result.extend(B)
    return result  # 返回合并后的列表

def MergeSort(A):  # 递归方式将A列表进行 归操作
    if len(A)<2:  # 当长度为0或1时
        return A  # 返回
    mid = len(A)//2  # 获得一半的长度
    left = MergeSort(A[:mid])  # 列表左半边进行归操作
    right = MergeSort(A[mid:])  # 列表右半边进行归操作
    return Merge(left, right)  # 将左半边和右半边的列表进行 并操作

a = MergeSort(a)  # 对a列表调用归并排序
for i in range(len(a)):  # 输入排序后的a列表
    print(a[i], end=" ")

# 使用桶排序方式编写
n = int(input())  # 输入n
a = [int(i) for i in input().split()]  # 输入a列表

def BucketSort(A, bucketcount):  # 定义桶排序函数
    minvalue, maxvalue = min(A), max(A)  # 找到最大值和最小值
    bucketsize = (maxvalue-minvalue+1)//bucketcount  # 计算桶的大小
    res = [[] for i in range(bucketcount+1)]  # 初始化bucketcount+1个桶
    for x in A:  # 遍历A列表中所有元素
        idx = (x-minvalue)//bucketsize  # 确定其所属的桶的下标
        res[idx].append(x)  # 加入到对应的桶中
    ans = []  # 定义结果数组
    for res_x in res:  # 遍历每个桶
        res_x = sorted(res_x)  # 每个桶单独排序
        ans += res_x  # 再将排序后的结果添加到ans列表中
    return ans  # 返回ans列表

a = BucketSort(a, min(1000, n))  # 对a列表调用桶排序
for i in range(len(a)):  # 输入排序后的a列表
    print(a[i], end=" ")

【运行结果】

5
1 5 9 3 7
1 3 5 7 9