蓝桥杯(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 123

 1.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))