蓝桥杯(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 = i
    for 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  #注意这个的设置比较重要，如果比到最后是最小的，则插入的位置是0
    for 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]的位置上！
            break
    a[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+1
    for i in range(left+1,right+1):
        if a[i]<stand:
            a[i],a[idx] = a[idx],a[i]
            idx = idx+1
    a[idx-1],a[left] = a[left],a[idx-1]
    #print(a)
    return idx-1
 
def quicksort(a,left,right):
    if left<right:
        mix = partition(a,left,right)
        quicksort(a,left,mix-1)
        quicksort(a,mix+1,right)
    return a
 
a = [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 c
 
def Mergesort(a):
    if len(a) < 2:
        return a
    else:
        mix = len(a) //2
        left = Mergesort(a[0:mix])
        right = Mergesort(a[mix:len(a)])
        a = Merge(left,right)
        return a
 
n = 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) // bucketsize
        res[idx].append(i)
    ans = []
    for i in res:
        i.sort()
        ans = ans + i
    return ans
 
n = int(input())
a = list(map(int, input().split()))
print(Bucket_sort(a,5))