【题目来源】
蓝桥云课：1.宝藏排序Ⅱ - 蓝桥云课 (lanqiao.cn)
【题目描述】
在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。
【输入】
输入第一行包括一个数字 \(n\)，表示宝藏总共有 \(n\) 个。
输入的第二行包括 \(n\) 个数字， 第 \(i\) 个数字 \(a[i]\) 表示第 \(i\) 个宝藏的珍贵程度。
【输出】
输出 \(n\) 个数字，为对宝藏按照珍贵程度从小到大排序后的数组。
【输入样例】
5
1 5 9 3 7
【输出样例】
1 3 5 7 9
【解题思路】
【算法标签】
《蓝桥云课 3226 宝藏排序II》 #思维# #排序#
【代码详解】
# 使用快速排序编写（与学而思教的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遍历至rightif a[i]<=a[left]: # 如果比基准值a[left]要小a[i],a[idx] = a[idx],a[i] # 与要交换的下标进行交换idx+=1 # idx自增1a[left],a[idx-1] = a[idx-1],a[left] # 最后将基准值与idx-1进行交换return idx-1 # 返回idx-1，其为middef 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