排序 (蓝桥杯) JAVA

题目描述：

---

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

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

答案：jonmlkihgfedcba

---

冒泡排序算法(排序数字，字符)：

理解:

冒泡排序的正序排序，整个实现过程，就类似气泡从水底，到水面的过程，即越到水面，气泡越大，在排序过程中也是如此，每次排序都会将数值最大的数，挪到数组后端。

冒泡排序正序排列数字代码如下：

   public static void maopao(int a[]) {for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}

冒泡排序正序排列字符代码如下：

public static void maopao(char a[]) {for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}

---

String与String buffer的区别:

思路：

在暴力破解的代码中我用到了StringBuffer存储字符串，为什么不用String存储呢，因为String储存的字符串有时候不可变动，StringBuffer可以。以下为两者在被函数调用的区别：

代码：

import java.nio.Buffer;public class text {public static void main(String[] args) {StringBuffer s = new StringBuffer("abcd");String s1 = "abcd";add(s);add(s1);System.out.println(s);System.out.print(s1);}public static void add(String s) {s = s + 'A';}public static void add(StringBuffer s) {s.append('A');}}

输出：

可以看出，StringBuffer,被调用后内容更新了，而String 没有被更新

以下是StringBuffer 的一些基本函数的用法：

1. delete(0 , 1) : 删除[0 , 1)区间内的字符
2. insert (0, 'a') : 将字符 a 插入0的位置
3. appand( 'a' ) :将字符a添加到末尾。

---

纯暴力破解(T到爆炸)：

解题思路：

所谓纯暴力，就是不加思索，直接用 dfs + 回溯思想，一个一个遍历直到找到符合条件的字符串。这里将冒泡排序进行了一些改进，让其能够记数：

冒泡排序记数代码如下：

 public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}

纯暴力完整代码如下：

import java.util.*;public class Main{public static char a[] = new char[26];public static boolean b[] = new boolean[26];public static void main(String[] args){ a[0] = 'a';for(int i = 1; i <= 25; i ++) {a[i] = (char)(a[i - 1] + 1);}StringBuffer s = new StringBuffer("ihgfedcba");for(int i = 0; i < 26; i ++) {b[i] = true;dfs(a[i], s);b[i] = false;s = s.delete(0, 1);}}public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}public static void dfs(char d, StringBuffer s) {s = s.insert(0, d);String s1 = new String(s);char c[] = s1.toCharArray();if(maopao(c) == 100) {print(s);return;}for(int i = 0; i < 26; i ++) {if(b[i] == false) {b[i] = true;dfs(a[i], s);b[i] = false;s.delete(0, 1);}}}public static void print(StringBuffer s) {System.out.println(s);}
}

大家也别运行这个代码了，我粗略地算了一下，要得出结果至少要 26！/ 10^9 / 3600 = …小时。 😭数据太大了不足以用年来计量了😭我只能说我是真SB。

---

暴力破解加思考(bingo)：

解题思路：

所以做这种填空题，纯暴力是吃力不讨好的，我们应该尽可能的大胆去思考，大胆去猜测，去举例论证，以减小我们搜索的范围。

1.首先明确题目要求，字符最少，且字典序最小,不能重复。
所以左端应该越接近a越好，例如：......dcba, 这种序列交换次数也很大，所以相应需要的字符也少。

对冒泡排序的核心代码进行分析:

对于上述推测的字符串类型，可以发现每次运行都会交换次序，我们可以用 cba，ba，带入冒泡排序去推规律，不难发现，交换次数 N = （x - 1 + x - 2 + x - 3 + … + 0）化简得到：N = x * (x - 1) / 2

可以算出 x = 15 时 N = 105。

也可以对上述纯暴力代码修改，让其输出，第一个大于 100 次交换次序的数列：

import java.util.*;public class Main{public static char a[] = new char[26];public static boolean b[] = new boolean[26];public static void main(String[] args){ a[0] = 'a';for(int i = 1; i <= 25; i ++) {a[i] = (char)(a[i - 1] + 1);}StringBuffer s = new StringBuffer("");for(int i = 0; i < 26; i ++) {b[i] = true;dfs(a[i], s);b[i] = false;s = s.delete(0, 1);}}public static int maopao(char a[]) {int sum = 0;for(int i = 0; i < a.length; i ++)for(int j = 0; j < a.length - i - 1; j ++) {if(a[j] > a[j + 1]) { char temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;sum ++;}}return sum;}public static void dfs(char d, StringBuffer s) {s = s.insert(0, d);String s1 = new String(s);char c[] = s1.toCharArray();if(maopao(c) >= 100) {print(s);return;}for(int i = 0; i < 26; i ++) {if(b[i] == false) {b[i] = true;dfs(a[i], s);b[i] = false;s.delete(0, 1);}}}public static int k = 1;public static void print(StringBuffer s) {if(k > 0)System.out.println(s);k --;}
}

输出：

-那么问题来了，上述字符串的交换次序是105
要想让交换次序变成100，有两种方案，1. 让一个字符少换5次，2.让5个字符都少交换1次，整体少交换5次

1.让一个字符少交换5次 :

即把某个字符往前移动即可：
例如：
onmlkjihgfedcba

让 o少交换5次

得nmlkjoihgfedcba刚好交换次数为100

这种方式如果将最后一个字母向前移动的话，是可以将字典序变小的。
我们再来看看让五个字符都少交换1次的方法。

2.让五个字符都少交换1次，整体少交换5次 :

即将onmlkjihgfedcba中某个字符向后移动，这样其他字符就会少交换一次

为了让交换后的字典序尽可能小，且满足交换次序为100次，我们最好是将中间某个字符放到尾部，这样字典序就小的更多。

满足上述要求我们发现将j交换到尾部刚好能满足条件即：

jonmlkihgfedcba
也就是我们的最终答案

---

总结：

这道题难度不言而喻，思维量很大，对我来说很难。所以，我们不能小看蓝桥杯的小题，没有把握的填空题可能真的没必要钻牛角尖去s扣它不放，而导致后面大题能骗或者搞到分的地方没有时间。适当放弃就要放弃，等能得的分都得到了，再来会会它也不迟，这里更是提醒我自己，我本人就爱怒怼一道题s扣不放。要明白，我们的目的是尽可能得我们能得的分，而不是将所有题做对。把我们的努力成果好好的发挥出来。能够权衡什么是西瓜什么是芝麻并灵活应对也是一个合格程序员该具备的能力不是么？😁