📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，多多关照😜😜😜
🏅🏅🏅2021年度博客之星TOP100,2021年度博客之星领域TOP5，Python领域优质创作者，欢迎大家找我合作学习（文末有VX 想进学习交流群or学习资料 欢迎+++）
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

前言：【Python训练营】是针对Python语言学习所打造的一场刷题狂欢party！ 对基础知识把握不牢固的话，欢迎参考此套课程：Python公开课 搭配使用最佳嗷~喜欢的话就抓紧订阅起来吧！🍋🍋🍋如果对学习没有自制力或者没有一起学习交流的动力，欢迎私信或者在文末添加我的VX，我会拉你进学习交流群，我们一起交流学习，报团打卡

@TOC

题目描述

题目描述：

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。 在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序， 总共需要 4 次交换。小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交换，可是他忘了吧这个字符串记下来，现在找不到了。请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中不可以包含相同的字符。

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个只包含小写英文字母的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

解题思路

• 因为是需要尽可能使用较短长度的字符串来构成100次的相邻字符的交换，并且要求字典序是最小的而且只能交换相邻的字母，所以我们需要使用尽可能使用排列在前面的字符，并且使用逆序排列；
• 冒泡排序的最坏情况是（全逆序的情况：54321），那么在这种情况下排序需要交换的次数是 n*(n-1)/2；
• 当n = 15 的时候需要交换的次数是105，当n = 14 的时候需要交换的次数是91次。考虑完全逆序的情况这样才可以使得字符串的交换次数尽可能多也就是字符串最短，那么需要长度为15的完全逆序的字符串；
• 因为完全逆序交换的次数为：(1 + 2 + … 14) * 14 = 105，所以剩下的我们就需要在完全逆序的字符串："onmlkjihgfedcba"进行调整使其构成能够使用100次的相邻字母的字符串；
• 105次只比100次多了5次，所以我们需要将其中多余的5次消除掉，分析字符串的特点可以知道后面字典序较大的字符往前调整，位于其前面的字符串的相对位置是不变的，**所以我们需要在逆序的"onmlkjihgfedcba"字符串第6个字母放到最前面，这样当排列好了"abcdefghi"之后j就位于其后面，**这样字母j这个位置是不用调整的，所以恰好消除了多余的5次，最后交换的次数为 14 + 13 + … + 6 + 4 + 3 + 2 + 1 = 100次。所以结果为：jonmlkihgfedcba。主要还是找出其中的规律，先考虑极端的情况再进行调整

源码分享

# Time    : 2022/2/8 23:08
# File    : 冒泡排序.py
# Author  : 是Dream呀！
# 微信VX   : Xu18300396393
# 一万次悲伤，依然会有Dream，我一直在最温暖的地方等你！
# 冒泡排序
def bullet(list1,count):
    for i in range(len(list1)-1):
        for j in range(len(list1)-1-i):
            if list1[j] > list1[j+1]:
                count += 1
                list1[j], list1[j+1] = list1[j+1], list1[j]
    return (list1,count)

count = 0
print(bullet(list('jonmlkihgfedcba'),count))

学习总结

1.冒泡排序基本结构：

def bullet(list1,count):
    for i in range(len(list1)-1):
        for j in range(len(list1)-1-i):
            if list1[j] > list1[j+1]:
                count += 1
                list1[j], list1[j+1] = list1[j+1], list1[j]

2.做题的时候还是有些题目要找出其中的规律，先考虑极端的情况再进行调整，这样会使题目方便很多。

🏅今天是我在Python训练营的第 15 天，希望每天都能见到最棒的你🏅

🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话，就不要吝惜你的一键三连了~