唐山房地产网站建设,奥美广告公司简介,长春住房和城乡建设部官方网站,wordpress小程序调用编程工作偶尔会遇到一些不常见问题需要处理#xff0c;学编程处理问题也难免需要熟悉一些算法以前学习的时候就遇到过一个看似简单的排序算法问题#xff0c;当时的解决办法是我没有用过的#xff0c;在此记录一下问题 - 英文字符串排序如下几个英文单词或者字母apple#…编程工作偶尔会遇到一些不常见问题需要处理学编程处理问题也难免需要熟悉一些算法以前学习的时候就遇到过一个看似简单的排序算法问题当时的解决办法是我没有用过的在此记录一下问题 - 英文字符串排序如下几个英文单词或者字母applecar afamilyskyapplicationappbabybackbackgroundbadbbbbbbeecafe cakecare排序后的结果是/**aappappleapplicationbabybackbackgroundbadbbbbbbeecafecakecarcarefamilysky**/规则逻辑通过结果可知a 与 app a排前面 (开头字母相同短的排在前面)back 与 backgroud back排在前面 (开头字母相同短的排在前面)application 与 baby application 排在前面(开头字母不同从a-z依次排序)设计实现a1 b2 c3 d4 e5 f6 g7 h8 i9 j10k11 l12 m13 n14 o15 p16 q17 r18 s19 t20u21 v22 w23 x24 y25 z26a代表的是 1b代表的是 2z 代表 26 就可以实现初步排序但是 bbbbb与 bee 两个单词要实现 bee 在前逻辑该怎么写呢起初想法是字母依次比较bbbbb 与 bee比较的第二个字母的时候 b 与 e 分别代表 2 和 5 所以bbbbb排前面问题是一个一个字母比较看起来很麻烦10个单词10个都要比较有以下解决方案都有用到递归方法一 通过单词获取权重进行排序(当初使用方法)bbbbb b 2 b2 b2 b2 b2bee b 2 e 5 e 5权重数 PxPx(bbbbb) 2 2 * 27^-1 2 * 27^-2 2 * 27^-3 2 * 27^-4 2.079Px(bee) 2 5 * 27^-1 5 * 27^-2 2.192通过这个计算方式可以获得权重值Px(bbbbb) Px(bee)所以 bbbbb 排在 baby 前面权重数27这里为什么是 27 不是26 是考虑到一种情况会导致排序失败比如 az 与 b比较Px(az) 1 26 * 26^-1 2Px(b) 2Px(az) Px(b) 显然是错的 将26 改为 27 就可避免这个错误优点不管是任何单词一千个也好得出每个字符串对应的权重值就能做到排序代码实现更新与2020-01-09后面做了优化区分字母大小写权重改为53public static void main(String[] args) {String[] noP {Baby,apple, car, A, family, B,b, Sky, application, app, baby, back, background,bad, bbbbb, bee, cafe, cake, care };String[] nopTop sortByWeights(noP);for (String string : nopTop) {System.out.print(string ,);}System.out.println();System.out.println(----------------------);for (String string : nopTop) {System.out.println(weights:\t getStrWeights(string,0) \t string);}}/*** for 权重排序**/public static String[] sortByWeights(String[] disorder) {double[] weightsArr new double[disorder.length];HashMap recordMap new HashMap();// 计算每个字符串的权重值for (int i0; iweightsArr[i] getStrWeights(disorder[i],0);recordMap.put(weightsArr[i],i);//保存权重值对应的字符串所在数组位置}// 将获取的权重值排序Arrays.sort(weightsArr);String[] sorderStr new String[disorder.length];int orderIndex 0;for (int i0; i// 拿出排好序的索引orderIndex recordMap.get(weightsArr[i]);sorderStr[i] disorder[orderIndex];}return sorderStr;}// 权重数值private final static double weightsNum 53;/*** for 计算字符串的权重值算法* param deep* param str* return weights*/public static double getStrWeights(String str,int deep) {int c str.charAt(deep);boolean isUppercase true;if(c 97) {c c - 32;isUppercase false;}c c - 64; // A,a - 1; B,b - 2int molecular c*2;if(isUppercase) molecular--; //if(B) - 3;if(b) - 4; for end [Baby,baby]// 这里考虑了大小写 如果字母是B 权重3/53 小写b 权重4/53 使小大小写也能排序double weights molecular/ (Math.pow(weightsNum, deep));return deep str.length() ? weights : weights getStrWeights(str,deep); //递归到字符串末尾}运行main方法控制台输出结果A,app,apple,application,B,Baby,b,baby,back,background,bad,bbbbb,bee,cafe,cake,car,care,family,Sky,----------------------weights:1.0Aweights:2.6151655393378426appweights:2.615328013590046appleweights:2.615329041941876applicationweights:3.0Bweights:3.0394956910738395Babyweights:4.0bweights:4.0394956910738395babyweights:4.040019613506452backweights:4.0400214752701284backgroundweights:4.0405838376646495badweights:4.076923067174232bbbbbweights:4.192239231043076beeweights:6.042075001511314cafeweights:6.045634987271372cakeweights:6.050551797792809carweights:6.050618967335452careweights:12.047115878410484familyweights:37.43289426842293Sky缺点考虑到前一种算法的计算如果单词长度超过20或者更长会导致计算量很大的问题如果有一百个单词比较计算很有必要如果只有两个单词bbbbbbbbbbbbbbbb 与 bar 比较 用权重法不合适因为只有两个单词没比较计算这么多就能得出排序结论下面就讲讲另一种排序算法方法二 逐个字母计算排序下面说一下新思路逐个比较applecar afamilyskyapplicationappbabybackbackgroundbadbbbbbbeecafe cakecare还是上面的单词首先获取每个字符串的第一个字母第一个字母为 a 的 全部取出apple a application app比较他们的第二个字母 a 没有第二个字母自然排在最前面依次类推使用递归即可完成排序因为临时想到的一种排序方法用到了TreeSet HashMap ArrayList 工具类感觉还可以后期优化。代码如下package javabasis.algorithm;import java.util.ArrayList;import java.util.List;import java.util.Set;import java.util.TreeMap;/*** 字段排序算法** author Narule**/public class StringAlgorithm {/*** 逐个字母比较排序** param disorder* return orderly*/public static String[] nopTop(String[] disorder) {int index 0;int end disorder.length;String[] orderly new String[end]; // 新建排序后的数组TreeMap treeMap new TreeMap(); // 排序工具类key是按照大小排序的List list null;// 收集字符串首字母信息for (String str : disorder) {char cTag str.charAt(0);list treeMap.get(cTag);if (list null) {list new ArrayList(1);}list.add(str);treeMap.put(cTag, list);}// 通过收集的首字母信息给字符串排序Set keySet treeMap.keySet();for (char cTag : keySet) {list treeMap.get(cTag);if (list ! null list.size() 0) {if (list.size() 2) { // 如果只有一个字符串不需要递归for (String string : list) {orderly[index] string;index;}} else { // 如果有两个以上字符串开头字母相同可能需要递归排序ArrayList arrayList new ArrayList(0);for (String string : list) {if (string.length() 1) { // 字符串长度大于2的需要添加到list,准备下一次递归排序用到arrayList.add(string.substring(1));} else {orderly[index] string;index;}}if (arrayList.size() 1) {String[] array new String[arrayList.size()];int i 0;for (String string : arrayList) {array[i] string;i;}array nopTop(array); // 还需要递归排序 back background - ack ackgroundfor (String string : array) {orderly[index] cTag string;index;}} else if (arrayList.size() 1) {orderly[index] cTag arrayList.get(0);index;}}}}treeMap.clear();return orderly; // 排序后的字符串数组}public static void main(String[] args) {String[] noP { apple, car, a, family, sky, application, app, baby, back, background,bad, bbbbb, bee, cafe, cake, care };String[] nopTop nopTop(noP);for (String string : nopTop) {System.out.println(string);}}}此方法用到TreeMap,这是Java工具类自带排序效果对此有疑问可以查看java源代码或介绍文档优点没有很大的计算量缺点使用TreeMap ArrayList 对象递归过多也会出现内存损耗过大或者溢出的情况未完后期待优化
