备战蓝桥——基础算法之排序-拓冰建站

本系列博客在于备战蓝桥杯，小伙伴们一起加油！

一.冒泡排序

#1.冒泡排序,时间复杂度O(n^2),空间复杂度O(1)，每次找到最大值或最小值放到最后
n=int(input())
a=list(map(int,input().split()))
#外循环n-1次
for i in range(1,n):for j in range(0,n-i):if a[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]
print(' '.join(map(str,a)))

二.选择排序

#2.选择排序,时间复杂度O(n^2),空间复杂度O(1),每次找到剩余最小的元素排到首位
n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):min_value=a[i]min_index=ifor j in range(i+1,n):if a[j]<min_value:min_value=a[j]min_index=ja[i],a[min_index]=a[min_index],a[i]
print(' '.join(map(str,a)))

三.插入排序

#3.插入排序，时间复杂度O(n^2),空间复杂度O(1)，抓扑克牌原理：每一张扑克牌插入到已经有序的数组中,最佳方法是从后向前比较
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n):j=i-1key=a[i]while j>=0 and key<a[j]:a[j+1]=a[j]j-=1a[j+1]=keyprint(' '.join(map(str,a)))

四.快速排序

#4.快速排序，找一个基准值，将数字拆分成三部分，小于基准值部分，等于基准值，大于基准值部分。然后递归求解。时间复杂度O(nlogn),空间复杂度O(logn)
def partition(a,left,right):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#最后把前半部分与left对调:a[idx-1],a[left]=a[left],a[idx-1]return idx-1
def quicksort(a,left,right):if left<right:#这句是必要的，要判断是否结束递归(判断有没有必要进行继续排序)mid=partition(a,left,right)quicksort(a,left,mid-1)quicksort(a,mid+1,right)n=int(input())
a=list(map(int,input().split()))
#我们把left当作基准值:
quicksort(a,0,n-1)#这里的左右是切片下标
print(' '.join(map(str,a)))

五.归并排序

# 5.归并排序，时间复杂度O(nlogn),空间复杂度O(n)
def Merge(a,b):#合并两个有序列表result=[]while(len(a)!=0 and len(b)!=0):if a[0]<=b[0]:result.append(a.pop(0))else:result.append(b.pop(0))result.extend(a)result.extend(b)return resultdef MergeSort(a):if len(a)<2:return amid=len(a)//2left=MergeSort(a[:mid])right=MergeSort(a[mid:])return Merge(left,right)n=int(input())
a=list(map(int,input().split()))
#我们把left当作基准值:
a=MergeSort(a)#这里的左右是切片下标
print(' '.join(map(str,a)))

六.桶排序

#6.桶排序
#核心在于将不同数据分散在不同的桶内，桶内进行排序，最后合并所有桶。桶排序要求数据尽可能分散，桶越多排序速度越快，但空间也会相应增大
def BucketSort(a,bucketcount):""":param a: 排序列表:param bucketcount:桶的数目:return:"""min_val=min(a)max_val=max(a)bucketsize=max(1,(max_val-min_val+1)//bucketcount)res=[[]for _ in range(bucketcount+1)]for x in a:idx=(x-min_val)//bucketsizeres[idx].append(x)ans=[]for r in res:r.sort()ans+=rreturn ansn=int(input())
a=list(map(int,input().split()))
#我们把left当作基准值:
a=BucketSort(a,1000)#这里的左右是切片下标
print(' '.join(map(str,a)))

或者

def BucketSort(a,bucketcount):""":param a: 排序列表:param bucketcount:桶的数目:return:"""min_val=min(a)max_val=max(a)bucketsize=(max_val-min_val+1)//bucketcountres=[[]for _ in range(bucketcount+1)]for x in a:idx=(x-min_val)//bucketsizeres[idx].append(x)ans=[]for r in res:r.sort()ans+=rreturn ansn=int(input())
a=list(map(int,input().split()))
#我们把left当作基准值:
a=BucketSort(a,min(1000,len(a)))#这里的左右是切片下标
print(' '.join(map(str,a)))