蓝桥杯历年真题题解----2020年-- 排序

简介: 蓝桥杯历年真题题解----2020年-- 排序

排序

题目链接

题目

题目描述

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。

冒泡排序中,每次只能交换相邻的两个元素。

小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个字符, 则在所有可能的排序方案中,冒泡排序的总交换次数是最少的。

例如,对于字符串 lan 排序,只需要 11次交换。对于字符串 qiao 排序,总共需要 4次交换。

小蓝找到了很多字符串试图排序,他恰巧碰到一个字符串,需要 100 次交 换,可是他忘了吧这个字符串记下来,现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串,对 该串的字符排序,正好需要 100 次交换。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。

运行限制

最大运行时间:1s

最大运行内存: 128M

解题思路

对于一个完全乱序(即与排完序的序列相反)的序列进行冒泡排序所需要的交换次数为:

比如N为序列的个数

则(N-1 + 1) *(N-1)/ 2为排序完成所需要的次数

对于 4321 排序后 1234

第一轮 需要 3次

第二轮 需要2次

第三轮 需要1次

一共需要n-1轮

总的次数为:1+2+3 = (4-1 + 1)* 3 / 2

根据运算公司长度为15完全乱序的字母序列需要105,而长度为14需要91

所以需要abcdefghijklmno这15个字母(字典序最小)的倒序,需要少5次交换所以j向前提到第一位

答案为

jonmlkihgfedcba

j提前可以少5次交换

目录
打赏
0
0
0
0
17
分享
相关文章
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯真题宝藏排序详解 | 冒泡排序 选择排序 插入排序
蓝桥杯真题宝藏排序详解 | 冒泡排序 选择排序 插入排序
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
10月前
蓝桥杯真题代码记录(数位排序
蓝桥杯真题代码记录(数位排序
68 0
蓝桥杯历年真题题解----2020年-- 子串分值和
蓝桥杯历年真题题解----2020年-- 子串分值和
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等