5.1 字符串排序

5 String

本章内容

• 5.1/5.2: 字符串排序
• 5.3: 子字符串查找-KMP算法
• 5.4: 正则表达式

5.0.1 Java中关于String类的规定

• String对象由一系列char组成,char为16bits
• 不可变性:String对象不可变,因此可用于赋值,作为参数或返回
• 子字符串:Java中substring()方法实现了提取子字符串,可在常数时间完成,原理参考下图
• 字符数组Char[]和String的比较 | 操作 | 字符数组 | 字符串 | | :—-: | :—-: | :—-: | | 声明 | Char[] a | String s | | 访问字符 | a[i] | s.charAt(i) | | 字符串长度 | a.length | s.length() | | 转换 | a=s.toCharArray() | s=new String(a) |

5.1 字符串排序

5.1.1 键索引计数

• 描述:不同字符串按组分类,组的编号是一个较小的整数,算法根据编号对字符串排序
• 适用情况:小整数键索引的字符串

• 步骤:

  1. 频度统计(N个字符串)

     for(i=0; icount[a[i].key()+1]++;

  2. 频度->索引

     for(int r=0; rcount[r+1] += count[r];

  3. 数据分类:字符串移动到辅助数组中排序

     for(int i=0; iaux[count[a[i].key()]++] = a[i];

  4. 写回

     for(int i=0; ia[i] = aux[i];

实现

int N = a.length;
String[] aux = new String[N];
int[] count = new int[R+1];
//四个步骤....

算法分析

• 命题:键索引计数法排序N个键值为0-R-1间整数的元素需要访问数组11N+4R+1次

证明:数组初始化是访问N+R+1次,步骤一:2N次;步骤二:2R次;步骤三:3N次,步骤四:2N次

5.1.2 低位优先的字符串排序(LSD)(算法5.1)

5.1.3 高位优先的字符串排序(MSD)(算法5.2)

5.1.4 三向字符串快速排序(算法5.3)