上一篇:高位优先的字符串排序
该算法思路与高为优先的字符串排序算法几乎相同,只是对高位优先的字符串排序算法做了小小的改进。
思路:根据键的首字母进行三向切分,然后递归地将三个子数组进行排序。...三向字符串快速排序实现并不困难,只需对三向快排代码做些修改即可:
代码中的charAt(String[] a,int d)方法是获取下标d处的字符,exch()是交换函数。...sort(a,lo,lt-1,d);
if(v>=0) sort(a,lt,gt,d+1);
sort(a,gt+1,hi,d);
}
}
相对于高位优先字符串算法的优点...:
高位优先字符串算法可能会创建许多的空数组(前缀相同的情况下),但本算法总是只有三个;
本算法不需要额外的空间。...要将含有N个字符串的数组排序,三向字符串快速排序需要比较字符~NlnN次。