蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
冒泡排序:
def bubble_sort(li): # 函数方式for i in range(len(li)-1):exchange=Falsefor j in range(len(li)-i-1):if li[j]>li[j+1]:li[j],li[j+1]=li[j+1],li[j]exchange=Trueif not exchange:return选择排序:
从左往右找到最小的元素，放在起始位置；重复上述步骤,依次找到第2小、第3小元素...
第0次循环从[0,n-1]中找最小元素a[x]，与a[0]交换
第1次循环从[1,n-1]中找最小元素，与a[1]交换
第2次循环从[2,n-1]中找最小元素，与a[2]交换
第i次循环从[i,n-1]中找最小元素，与a[i]交换
第n-2次循环从[n-2,n-1]中找最小元素，与a[n-2]交换时间复杂度:O(n'2)，空间复杂度O(1)，稳定
n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1): # 一共n-1次!min = i # 每次默认第一个值为最小值for j in range(i + 1, n):if a[j] < a[min]:min = ja[i], a[min] = a[min], a[i]print(' '.join(map(str, a)))插入排序:
第一个元素看做已排序,从左往右遍历每一个元素:
在已排序元素中从后往前扫描 : 如果当前元素大于新元素，则该元素移动到后一位
重复第二步直至找到小于等于新元素则停止。
将上述步骤看做摸牌,每次摸一张牌从后往前判断是否可以插入
对于第i张牌a[i],[0, i-1]中的牌都是已经排好顺序的
从后往前逐个判断ai]是否大于a[i]
如果a[i]>a[i]:则a[i]往后挪一个位置；如果a[i]<=a[i]:此时在aj+1]的位置放置a[i]
时间复杂度:O(n^2)，空间复杂度O(1)，不稳定
for i in range(1,len(li)): # 功n-1趟,i表示摸到牌的下标tmp=li[i] # 每次摸的牌j=i-1 # 手里最右侧的while j>=0 and li[j]>tmp: # 一直往左走li[j+1]=li[j] # 右移j-=1li[j+1]=tmp # 选好位置了