@No.HJ26 字符串排序
@problem description:编写一个程序，将输入字符串中的字符按如下规则排序。
规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
如，输入： Type 输出： epTy
规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入： BabA 输出： aABb
规则 3 ：非英文字母的其它字符保持原来的位置。
如，输入： By?e 输出： Be?y
注意有多组测试数据，即输入有多行，每一行单独处理（换行符隔开的表示不同行）
@input description:输入字符串@output description:
输出字符串
示例
@input:A Famous Saying: Much Ado About Nothing (/8).@output:
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (/8).
while(str = readline()){var arr = str.split("");var arr1 = [];var arr2 = [];for(var i=0;i<arr.length;i++){if(arr[i] < 'A' || (arr[i] > 'Z' && arr[i] < 'a') || arr[i] > 'z'){arr1.push([i,arr[i]]);}else{arr2.push([i,arr[i]]);};};arr2.sort(function(a, b){var x = a[1].toLowerCase(), y = b[1].toLowerCase();return x < y ? -1 : x > y ? 1 : a[0] - b[0];});for(var i=0;i<arr2.length;i++){arr.splice(i,1,arr2[i][1]);};for(var i=0;i<arr1.length;i++){arr.splice(arr1[i][0],0,arr1[i][1]);};arr.length = str.split("").length;console.log(arr.join(""));};
算法分析：
这道题真的好多坑，先分析我最后的正确答案思路（最后附上我踩坑的经历）：
由于字符串中需要处理的有两部分，大小写英文字母和其他字符，所以第一个for循环就先把它们分离成两个数组，同时也保存好字符在原字符串中的位置下标。
核心来了：对大小写字母的排序问题（arr2）：
使用sort()方法，传入一个排序器函数：内部对字母进行全大写处理，然后确定返回值：
x < y ? -1 : x > y ? 1 : a[0] - b[0]：三目运算符的套用，细节规定了字符值相同的时候，比较原数组下标大小；最后再把两个数组重新插回原数组对应位置即可。
注意看清题目是有多次输入，对应的代码就需要多次来接收。
Code_Zevin_J —— -08-06 16:48:22
踩坑经历👇（大佬请无视）
1. 输出结果不同：Node.js环境 —— JavaScript（V8 6.0.0）环境
我先是在vscode里编写的如下第一版代码，测试结果也是正确的。
var str = "A Famous Saying: Much Ado About Nothing (/8).";var arr = str.split("");var arr1 = [];for(var i=0;i<arr.length;i++){if(arr[i] < 'A' || (arr[i] > 'Z' && arr[i] < 'a') || arr[i] > 'z'){arr1.push([i,arr[i]]); // 把非字母字符抽离到一个新的数组中。格式为：[原数组下标，字符值]arr.splice(i,1,"~"); // 在原数组的位置替换成"~"};};arr.sort(function(a, b){// 不分大小写的字典顺序排列var x = a.toLowerCase(), y = b.toLowerCase();return x < y ? -1 : x > y ? 1 : 0;});for(var i=0;i<arr1.length;i++){arr.splice(arr1[i][0],0,arr1[i][1]);};// 字母排序完成后把特殊字符再插到原来的位置arr.length = str.split("").length; // 截取掉之前添加的所有"~"console.log(arr.join(""));
之后粘到牛客网上的编辑器窗口里运行。显示没通过所有的测试用例，细看那个未通过的用例，我突然发现怎么输出结果和在vscode里不一样？？？
仔细比对后发现原来是字母相同的部分排列顺序有出入…啊…这…(ˉ▽ˉ；)…
摘出sort排序那一段，字母相同情况下返回 0 ，即为不排序，按正常思维不都是值相等默认按原顺序排列不动嘛，这咋乱序了捏…
arr.sort(function(a, b){// 不分大小写的字典顺序排列var x = a.toLowerCase(), y = b.toLowerCase();return x < y ? -1 : x > y ? 1 : 0;});
这什么操作？？？立马联想起来这可能是因为两者的执行环境不同：
vscode里我用的是Node.js环境，而浏览器里的是JavaScript（V8 6.0.0）环境。
百度一番发现，这确实跟Google浏览器的v8引擎有关，Array.sort()排序在v8引擎中可能会存在乱序的BUG：具体的原因是为了高效排序，称之为不稳定排序 ——数组长度超过10之后会调用另一种排序方法（插入排序），10以下用的是快速排序算法。
所以就是：数组长度在10以下两种环境就不会出现差异，10以上在Google浏览器中就会出现同值乱序的问题。
我们来验证一下：先输入一共10个字符（8个大小写不同的A和两个空格字符）：按以上结论应该会原样输出，通过测试。
果然是这样，然后追加一个 b，这样数组长度就超过10了，运行发现果然之前的A都乱序了。
解决方案
找到问题后，怎么改进代码来避免这个问题呢？开头的代码其实已经给出了答案。具体方案为：
在分离字符的时候也保存每个字符在原数组中的位置下标。在字符值相同的情况下，就可以比较两者原数组下标来排序。
for(var i=0;i<arr.length;i++){if(arr[i] < 'A' || (arr[i] > 'Z' && arr[i] < 'a') || arr[i] > 'z'){arr1.push([i,arr[i]]);}else{arr2.push([i,arr[i]]);};};arr2.sort(function(a, b){var x = a[1].toLowerCase(), y = b[1].toLowerCase();return x < y ? -1 : x > y ? 1 : a[0] - b[0];});
刚才出错的用例也顺利通过了！！！但是又出现了第二个问题——
2. 多次输入传值问题
继续提交发现，还是没通过，这次什么也没有输出，按理说应该输出多行结果丫？
一直以来我都忽略了题目中的一个点：
注意有多组测试数据，即输入有多行，每一行单独处理（换行符隔开的表示不同行）
之后我一直在纠结怎么按照换行符来分割字符串，有点魔怔了。。。后来发现这根本不现实，因为js中读取输入用的是readline模块方法（有关readline的详解请看：）
【linux系统（ubuntu16.04）】Node.js中使用npm命令安装readline-sync模块实现用户键盘输入
换行符隔开的表示不同行，并不是输入了一个字符串。所以根本不用分割，直接多次接收即可。这里再说一个多次接收输入的小技巧：
在代码块外围包裹一个while循环，小括号里填上readline语句即可。
while(str = readline()){代码块};
到这里才算彻底写好这个算法，呼~
啰嗦了一大堆，不会吧，不会吧，真有人这么耐心看到这里了？！？
❤❤❤❤❤ ❤❤ ❤
【JavaScript——牛客网算法No.HJ26】字符串排序（字符串里英文字母按字典顺序重新排列 其他字符保持原位）附：详细排坑经历
