题解 | #字符串排序#
字符串排序
https://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584
// 快速排序有bug,NnN排序不稳定,没找到原因,推荐使用冒泡排序,快排这里浪费太久时间了,这里的快排不稳定(不明原因) /* const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); function f_sort(arg) { let left = 0; let chars = arg.split(""); // 将字符串转化为单个字符的数组 let alphas = chars.filter((item) => /[a-z]/gi.test(item)); let right = alphas.length - 1; let charCodeNum = alphas.map(item => item.toLowerCase().charCodeAt(0)) console.log(alphas) console.log(chars) fast_sort(charCodeNum,alphas, left, right); for (let m = 0; m < chars.length; m++) { if (!/[a-z]/gi.test(chars[m])) { alphas.splice(m, 0, chars[m]); } } return alphas; } function fast_sort(arg,target, left, right) { if (left < right) { const mid = partition(arg,target, left, right); fast_sort(arg,target, left, mid - 1); fast_sort(arg,target, mid + 1, right); } } function partition(arg,target, left, right) { let i = left; let pivot = right; for (let j = i; j < pivot; j++) { if (arg[j] <= arg[pivot]) { [arg[i], arg[j]] = [arg[j], arg[i]]; [target[i], target[j]] = [target[j], target[i]]; i++; } } [arg[i], arg[pivot]] = [arg[pivot], arg[i]]; [target[i], target[pivot]] = [target[pivot], target[i]]; return i; } rl.on("line", function (line) { const res = f_sort(line); console.log(res.join("")); }); */ // 冒泡排序版本(稳定) const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); function b_sort(arg) { let left = 0; let chars = arg.split(""); // 将字符串转化为单个字符的数组 let alphas = chars.filter((item) => /[a-z]/gi.test(item)); let right = alphas.length - 1; let charCodeNum = alphas.map(item => item.toLowerCase().charCodeAt(0)) bubble_sort(charCodeNum,alphas,alphas.length); for (let m = 0; m < chars.length; m++) { if (!/[a-z]/gi.test(chars[m])) { alphas.splice(m, 0, chars[m]); } } return alphas; } function bubble_sort(arg,target,length) { for(let i=length;i>1;i--){ let swapper = 0 for(let j=1;j<i;j++){ if(arg[j-1] > arg[j]){ swapper = 1; [arg[j],arg[j-1]] = [arg[j-1],arg[j]]; [target[j],target[j-1]] = [target[j-1],target[j]]; } } if(!swapper){ break } } } rl.on("line", function (line) { const res = b_sort(line); console.log(res.join("")); });