算法4 Java解答 5.1.2

HuGuoDong
技术, 归档
Page content

5.1.2

问题：

给出使用地位优先的字符串排序算法处理下面这些键的轨迹

no is th ti fo al go pe to co to th ai of th pa

Give a trace for LSD string sort for the keys:

no is th ti fo al go pe to co to th ai of th pa

分析：

LSD 适用于字符等长的数组排序。

从右往左，依次数组中每个元素对位置d的字符使用key-indexed counting排序。

平均数组访问次数7WN+3WR。额外空间N+R。 N 对应aux数组，R对应count数组。 对于一般的应用LSD线性时间复杂度。

public static void sort(String[] a, int w) {
  int N = a.length;
  int R = 256;
  String[] aux = new String[N];
  for (int d = w - 1; d >= 0; d--) { // sort by key-indexed counting on dth char
    show(a);
    int[] count = new int[R + 1];
    for (int i = 0; i < N; i++) {
      count[a[i].charAt(d) + 1]++; // compute frequency counts
    }
    for (int r = 0; r < R; r++) {
      count[r + 1] += count[r]; // transforms counts to indices
    }
    for (int i = 0; i < N; i++) {
      aux[count[a[i].charAt(d)]++] = a[i]; // distribute
    }
    for (int i = 0; i < N; i++) {
      a[i] = aux[i]; // copy back
    }
  }
}

轨迹如下：

no	is	th	ti	fo	al	go	pe	to	co	to	th	ai	of	th	pa
pa	pe	of	th	th	th	ti	ai	al	no	fo	go	to	co	to	is
ai	al	co	fo	go	is	no	of	pa	pe	th	th	th	ti	to	to

参考：