您的位置:首页 > 财经 > 产业 > 【例题】lanqiao3226 宝藏排序Ⅱ

【例题】lanqiao3226 宝藏排序Ⅱ

2024/11/4 1:11:13 来源:https://blog.csdn.net/m0_73676887/article/details/142302061  浏览:    关键词:【例题】lanqiao3226 宝藏排序Ⅱ

在这里插入图片描述
样例输入

5
1 5 9 3 7

样例输出

1 3 5 7 9

解题思路

这里的n≤10^5,说明O(n ^2)的算法行不通。

基于比较的高效算法和基于数值划分的高效算法全部参考这篇文章

代码

最简单的自带排序

n=int(input())
a=list(map(int,input().split()))a.sort()
print(' '.join(map(str,a)))

利用桶排序

n=int(input())
a=list(map(int,input().split()))def bucket_sort(a,bucket_num):minval,maxval=min(a),max(a)# 桶大小bucket_size=(maxval-minval+1)//bucket_numbucket=[[] for i in range(bucket_num+1)]for x in a:bucket_idx=(x-minval)//bucket_sizebucket[bucket_idx].append(x)# 每个桶单独排序ans=[]for b in bucket:b.sort()ans+=breturn ansa=bucket_sort(a,5)
print(' '.join(map(str,a)))

归并排序

n=int(input())
a=list(map(int,input().split()))def merge(l,r):merged=[]l_id=0r_id=0while l_id<len(l) and r_id<len(r):if l[l_id]<=r[r_id]:merged.append(l[l_id])l_id+=1else:merged.append(r[r_id])r_id+=1merged.extend(l[l_id:])merged.extend(r[r_id:])return merged
def merge_sort(lst):if len(lst)<=1:return lstmid=len(lst)//2l=merge_sort(lst[:mid])r=merge_sort(lst[mid:])return merge(l,r)a=merge_sort(a)
print(' '.join(map(str,a)))

快速排序

n=int(input())
a=list(map(int,input().split()))# 求出基准值的位置排序即可
def partition(a,left,right):#找基准值,为a[left]idx=left+1for i in range(left+1,right+1):if a[i]<=a[left]:a[i],a[idx]=a[idx],a[i]idx+=1#把前半部分的最后一个和基准值对调a[left],a[idx-1]=a[idx-1],a[left]#返回基准值坐标return idx-1
def quicksort(a,left,right):if left<right:mid=partition(a,left,right)#此时a分为三部分:a[left:mid],a[mid],a[mid+1:right+1]quicksort(a, left, mid-1)quicksort(a,mid+1,right)#只需要考虑怎么把当前的问题分成两个子问题           
quicksort(a, 0, n-1)
print(' '.join(map(str,a)))

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com