当前位置：首页 > article >正文

【C语言蓝桥杯每日一题】——排序

article 2024/11/13 14:57:27

【C语言蓝桥杯每日一题】—— 排序😎

前言🙌
- 排序🙌
总结撒花💞

😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，和大家分享【C语言蓝桥杯每日一题】——排序~这里利用了数组指针的方法知识，都是精华内容，可不要错过哟！！！😍😍😍

排序🙌

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交换，可是他忘了吧这个字符串记下来，现在找不到了。请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
在这里插入图片描述

解题思路分析： 😍

首先认真读题，然后分析.
题目表明了这个排序是利用冒泡排序的，因此我们需要寻找冒泡排序的比较次数规律。可以看到，对有N个字母的字符串时完全乱序时需要交换N*(N-1)/2次数。如果需要100次的交换，即最少需要15个字母。
要求字典序最小显然要取a-o这15个字典序最小的字母。
逆向思考字符串经过100次交换后得到正序字符串 abcdefghijklmno。而完全乱序的字符串onmlkjihgfedcba变成正序字符串需要105次交换。
这里先举个栗子：例如 54321，最后变成12345，需要交换10次。如果把3放到前面，即35421 ,让他排成升序 12345需要交换8次。分析可以发现，比3大的数交换次数减少一次，3和比3小的数交换次数不变。
所以，将105次减少到100次，只需要将 j 先提前放到最前面就Ok了，因为比 j 大的有5个字母。这样就能将105次交换减少到100次交换，也就符合题目要求了。
注意：这里数组需要开辟16个空间，因为还需要存放 \0。

解题源码分享： 😍

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i = 0;
    int t = 0;
    char str [16] = "onmlkjihgfedcba";
    for (i = 4; i >= 0; i--)
    {
        if (str[i] > str[i + 1])
        {
            t = str[i];
            str[i] = str[i + 1];
            str[i + 1] = t;
        }
    }
    printf("%s", str);
    return 0;
}