中值法排序及LexoRank排序算法简述
概述
在业务中经常会遇到用户拖拽排序的场景，那么拖拽后的结果肯定需要一个值来定义这个排序结果；
一般都是用存数字来代替；但当排序发生变更时，连续的数字不太好维护，比如1，2，3，将3拖拽到1和2之间时，这个sort值应该是多少呢；
如果引入浮点数，那么浮点数的精度会一直膨胀，而后端db中sort字段的精度一般是固定的，并且不能无限制膨胀；
所以在查找了相关资料后，最后采用的是中值法；
定义a,b,c三个sort分别是1000，2000，3000
当abc -> acb时c.sort = (a.sort + b.sort)/2
并在后端update这个sort时，比较前后的sort是否<=阈值数值，当<=时，进行重排；
即a.sort = 1000,c.sort = 2000,b.sort = 3000
同时增加版本号字段，增加乐观锁;
然后最优的是结合websocket等方案，进行多端同步（如果存在多端操作同一个拖拽泳道的话，比如飞书，腾讯在线文档这种）;
我这边因为开发排期等原因，综合比较下来只做了被动刷新（即使用version字段，在update sort时判断是否已经被其他人更新过了）
上述是中值法排序我的理解
LexoRank排序
在熟悉了中值法排序后，我发现了另一个排序方式；LexoRank排序，之前排序的sort是采用的纯数字，而LexoRank使用的字符串(字母+数字，比如77gf)；
简单了解下后，发现其本质还是中值法，只是在计算中值时会把字符串转成对应的十进制数；
比如下面12131和27ga的转换;
这里不敲文字了,贴下手算的步骤（好久没手算，生疏了-。-）
还有一份demo代码
packagecom.cloud.product.service.dto;importjava.math.BigInteger;publicclassLexoRank{privatefinal String alphabet;// e.g., "0123456789abcdefghijklmnopqrstuvwxyz"//当前字符集长度privatefinal int base;privatefinal int length;// 固定秩字符串长度publicLexoRank(String alphabet,int length){this.alphabet=alphabet;this.base=alphabet.length();this.length=length;}// 将秩字符串转换为 BigIntegerpublicBigIntegertoBigInt(String rank){BigInteger val=BigInteger.ZERO;for(int i=0;i<rank.length();i++){int idx=alphabet.indexOf(rank.charAt(i));if(idx<0)thrownewIllegalArgumentException("Invalid char in rank");val=val.multiply(BigInteger.valueOf(base)).add(BigInteger.valueOf(idx));}returnval;}// 将 BigInteger 转回固定长度的秩字符串（高位补零）publicStringfromBigInt(BigInteger val){BigInteger b=BigInteger.valueOf(base);char[]chars=newchar[length];BigInteger cur=val;for(int i=length-1;i>=0;i--){BigInteger[]dr=cur.divideAndRemainder(b);int idx=dr[1].intValue();chars[i]=alphabet.charAt(idx);cur=dr[0];}if(cur.compareTo(BigInteger.ZERO)>0){thrownewIllegalArgumentException("Value too large for length");}returnnewString(chars);}// 生成初始秩（例如中间值）publicStringinitialRank(){//计算当前sort池下，length下的最大至（即base进制下 base^length值）BigInteger max=BigInteger.valueOf(base).pow(length);BigInteger mid=max.divide(BigInteger.valueOf(2));returnfromBigInt(mid);}// 在 a 和 b 之间生成一个秩（假设 a < b）publicStringbetween(String a,String b){BigInteger va=toBigInt(a);BigInteger vb=toBigInt(b);if(va.compareTo(vb)>=0)thrownewIllegalArgumentException("a must be < b");BigInteger diff=vb.subtract(va);if(diff.compareTo(BigInteger.ONE)<=0){// 无可用间隙，需要重平衡（调用外部重平衡逻辑）thrownewIllegalStateException("No gap between ranks; rebalance required");}BigInteger mid=va.add(vb).divide(BigInteger.valueOf(2));returnfromBigInt(mid);}// 生成第一个或最后一个秩（可用于插入到头尾）publicStringbeforeFirst(){// 取最小可表示值的一半BigInteger min=BigInteger.ZERO;BigInteger max=BigInteger.valueOf(base).pow(length);BigInteger val=max.divide(BigInteger.valueOf(10));// 例如靠前一点returnfromBigInt(val);}publicStringafterLast(){BigInteger max=BigInteger.valueOf(base).pow(length);BigInteger val=max.subtract(max.divide(BigInteger.valueOf(10)));returnfromBigInt(val);}// 简单示例publicstaticvoidmain(String[]args){String alphabet="0123456789abcdefghijklmnopqrstuvwxyz";LexoRank lr=newLexoRank(alphabet,8);String r1=lr.initialRank();String r2=lr.afterLast();System.out.println("r1 = "+r1);System.out.println("r2 = "+r2);// 插入一个在 r1 和 r2 之间的秩String mid=lr.between(r1,r2);System.out.println("mid = "+mid);// 连续插入示例（注意可能触发 rebalance）try{String m2=lr.between(r1,mid);System.out.println("m2 = "+m2);}catch(IllegalStateException ex){System.out.println("需要重平衡: "+ex.getMessage());}}}