【例题】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)))