蓝桥杯(1):python排序
1 基础
1.1 输出
1.1.1 去掉输出的空格
print("Hello","World",123,sep="+")
print("hello",'world',123,sep='')
print('hello','world',123)
#输出结果
#Hello+World+123
#helloworld123
#hello world 1231.1.2 以不同的方式结尾
print("Hello","World",123,sep="+",end='apple')
print("hello",'world',123,sep='')
print('hello','world',123)
1.2 输入
input 是字符串类型
1.3 常量变量运算符
int转bool：非0是TRUE，0是FALSE【0和FLASE一一对】
运算符：//整除 %取余
关系运算符的结果：TRUE或FALSE！
2 冒泡排序
2.1 算法步骤
运行n-1次，每一次把最大的换到最后
时间复杂度：O(n^2) 空间复杂度：O(1)【没有用到新的空间，是在原来的空间上进行的】，稳定
2.2 代码实现
n = int(input())
a = list(map(int,input().split()))
#循环n-1次，每次获得第i大
for i in range(1,n):#每次比较a[j]和a[j+1]的大小，如果前面大就交换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)))
3 选择排序
3.1 算法步骤
选择一个最小的放在最左边，核心：选择并储存最小值
时间复杂度：O(n^2),空间复杂度o(1)，稳定
3.2 具体代码
n = int(input())
a = list(map(int,input().split()))
for i in range(0,n-1):min_value = a[i]min_idx = ifor j in range(0+i,n):if a[j] < min_value:min_value = a[j]min_idx = j#进行交换a[min_idx] = a[i]a[i]= min_value #或者写成 都可以哦！#a[min_idx],a[i] = a[i],a[min_idx]#print(a)
print(' '.join(map(str,a)))
4 插入排序
4.1 算法步骤
相当于扑克牌排序
要做的是在一个有序的数组插入一个数字！
4.2 具体代码
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n):value = a[i]insert_idx = 0 #注意这个的设置比较重要，如果比到最后是最小的，则插入的位置是0for j in range(i-1,-1,-1):if a[j] > value:a[j+1] = a[j] #向后挪else:insert_idx = j+1 #挪不动，说明这个值比a[j]大，则他应该在a[j+1]的位置上！breaka[insert_idx] = value
print(' '.join(map(str,a)))5 快速排序
5.1 算法步骤
这时3的位置是一定正确的！
核心：怎么选基准，怎么分，怎么递归
5.2 具体代码
#列表a，左端点为left,后端点为right
def partition(a,left,right):stand = a[left]idx = left+1for i in range(left+1,right+1):if a[i]<stand:a[i],a[idx] = a[idx],a[i]idx = idx+1a[idx-1],a[left] = a[left],a[idx-1]#print(a)return idx-1def quicksort(a,left,right):if left<right:mix = partition(a,left,right)quicksort(a,left,mix-1)quicksort(a,mix+1,right)return aa = [5,3,8,1,2,9,4,7,6]
left = 0
right = 8
print(quicksort(a,left,right))注意递归的规则是：一定要有结束条件！！！！！这就解释left<right存在的必要性！！！要不然就是死循环！！！
6 归并排序
6.1 算法步骤
6.2 具体代码
合并两个有序的列表，实际还是递归！！！
# 归并排序
# 第一步是变编写代码：合并两个有序的列表！！！！
def Merge(A,B):c = []while len(A) !=0 and len(B)!= 0:if A[0] <= B[0]:c.append(A[0])A.pop(0)else:c.append(B[0])B.pop(0)c.extend(A)c.extend(B)return cdef Mergesort(a):if len(a) < 2:return aelse:mix = len(a) //2left = Mergesort(a[0:mix])right = Mergesort(a[mix:len(a)])a = Merge(left,right)return an = int(input())
a = list(map(int,input().split()))
print(Mergesort(a))
7 桶排序
7.1 算法步骤
为了缩小问题规模！！！
7.2 具体代码
代码的最核心：分桶！！！
找到最大值和最小值，除以总的桶数
def Bucket_sort(a,bucketcount):minvalue, maxvalue = min(a),max(a)bucketsize = (maxvalue-minvalue+1) // bucketcount #均匀的分开res = [[] for i in range(bucketcount+1)]#要多一个桶 放不能整除的那些数字#把所有的元素放在对应的桶里for i in a:idx = (i-minvalue) // bucketsizeres[idx].append(i)ans = []for i in res:i.sort()ans = ans + ireturn ansn = int(input())
a = list(map(int, input().split()))
print(Bucket_sort(a,5))