蓝桥杯宝藏排序题目算法(冒泡、选择、插入)

@小森

发布于 2024-03-15 11:14:47

780

发布于 2024-03-15 11:14:47

文章被收录于专栏：xiaosenxiaosen

冒泡排序:

def bubble_sort(li):            # 函数方式
    for i in range(len(li)-1):
        exchange=False
        for j in range(len(li)-i-1):
            if li[j]>li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
                exchange=True
        
        if 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 = j
    a[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-=1
        li[j+1]=tmp   # 选好位置了

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-12-28，如有侵权请联系 cloudcommunity@tencent.com 删除

算法