▶ 书中第五章部分程序，包括在加上自己补充的代码，字母表类，字符串低位优先排序（桶排）
● 字母表类
package package01; import edu.princeton.cs.algs4.StdOut; public class class01
{
public static final class01 BINARY = new class01("01"); public static final class01 OCTAL = new class01("01234567"); public static final class01 DECIMAL = new class01("0123456789"); public static final class01 HEXADECIMAL = new class01("0123456789ABCDEF"); public static final class01 DNA = new class01("ACGT"); public static final class01 LOWERCASE = new class01("abcdefghijklmnopqrstuvwxyz"); public static final class01 UPPERCASE = new class01("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); public static final class01 PROTEIN = new class01("ACDEFGHIKLMNPQRSTVWY");// 蛋白质？ public static final class01 BASE64 = new class01("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"); public static final class01 ASCII = new class01(128); public static final class01 EXTENDED_ASCII = new class01(256); public static final class01 UNICODE16 = new class01(65536); private char[] alphabet; // 索引 -> 字母
private int[] inverse; // 字母 -> 索引
private final int R; // 字母表基数 public class01(String alpha) // 从字符串生成一个字母表
{
boolean[] unicode = new boolean[Character.MAX_VALUE]; // 检查输入字符串是否有重复字母
for (int i = 0; i < alpha.length(); i++)
{
char c = alpha.charAt(i);
if (unicode[c])
throw new IllegalArgumentException("\n<Constructor> repeated character = '" + c + "'.\n");
unicode[c] = true;
}
alphabet = alpha.toCharArray();
R = alpha.length();
inverse = new int[Character.MAX_VALUE];
for (int i = 0; i < inverse.length; i++)
inverse[i] = -1;
for (int c = 0; c < R; c++)
inverse[alphabet[c]] = c;
} private class01(int radix) // 从基数生成一个字母表
{
R = radix;
alphabet = new char[R];
inverse = new int[R];
for (int i = 0; i < R; i++) // 正反向都初始化为 0 ~ R-1
alphabet[i] = (char)i;
for (int i = 0; i < R; i++)
inverse[i] = i;
} public class01() // 默认构造扩展 aSCII
{
this(256);
} public boolean contains(char c)
{
return inverse[c] != -1;
} public int radix()
{
return R;
} public int lgR() // 表示字母表所需要的二进制位数
{
int lgR = 0;
for (int t = R - 1; t > 0; t <<= 1)
lgR++;
return lgR;
} public int toIndex(char c) // 字符转索引
{
if (c >= inverse.length || inverse[c] == -1)
throw new IllegalArgumentException("\n<toIndex> c >= inverse.length || inverse[c] == -1.\n");
return inverse[c];
} public int[] toIndices(String s) // 字符串转数组
{
char[] source = s.toCharArray();
int[] target = new int[s.length()];
for (int i = 0; i < source.length; i++)
target[i] = toIndex(source[i]);
return target;
} public char toChar(int index)
{
if (index < 0 || index >= R)
throw new IllegalArgumentException("\n<toChar> index < 0 || index >= R.\n");
return alphabet[index];
} public String toChars(int[] indices) // 数组转字符串
{
StringBuilder s = new StringBuilder(indices.length); // 使用 StringBuilder 类，防止平方级时间消耗
for (int i = 0; i < indices.length; i++)
s.append(toChar(indices[i]));
return s.toString();
} public static void main(String[] args)
{
int[] encoded1 = class01.BASE64.toIndices("NowIsTheTimeForAllGoodMen");
String decoded1 = class01.BASE64.toChars(encoded1);
StdOut.println(decoded1); int[] encoded2 = class01.DNA.toIndices("AACGAACGGTTTACCCCG");
String decoded2 = class01.DNA.toChars(encoded2);
StdOut.println(decoded2); int[] encoded3 = class01.DECIMAL.toIndices("01234567890123456789");
String decoded3 = class01.DECIMAL.toChars(encoded3);
StdOut.println(decoded3);
}
}
● 字符串低位优先排序（桶排）
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01
{
private static final int BITS_PER_BYTE = 8; private class01() { } public static void sort(String[] a, int w) // 每个字符串定长 w 的字符串数组排序
{
int n = a.length;
int R = 256; // 默认基数
String[] aux = new String[n]; for (int d = w - 1; d >= 0; d--) // 从最后一位起，每次循环处理一位
{
int[] count = new int[R + 1];
for (int i = 0; i < n; i++) // 桶计数，这里 count[0] 和 count [1] 暂时为 0
count[a[i].charAt(d) + 1]++;
for (int r = 0; r < R; r++) // 规约前缀和，完成后字母 c 在排序中的起始下标是 count[toIndex[c]]，count[0] 固定为 0
count[r + 1] += count[r];
for (int i = 0; i < n; i++) // 向临时数组 aux 写入数据
aux[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < n; i++) // 排序完成的数组写回原数组
a[i] = aux[i];
}
} public static void sort(int[] a) // 有符号数组排序，以一个 Byte 为键
{
final int BITS = 32; // int 类型占 256 Bit
final int R = 1 << BITS_PER_BYTE; // 每个 Byte 表示 0 ~ 255
final int MASK = R - 1; // 0xFF，用于只保留最低位的蒙版
final int w = BITS / BITS_PER_BYTE; // int 类型占 4 Byte int n = a.length;
int[] aux = new int[n];
for (int d = 0; d < w; d++)
{
int[] count = new int[R + 1];
for (int i = 0; i < n; i++)
{
int c = (a[i] >> BITS_PER_BYTE * d) & MASK; // 保留从右往左数第 d 个 Byte
count[c + 1]++;
}
for (int r = 0; r < R; r++)
count[r + 1] += count[r];
if (d == w - 1) // 符号位，0x00-0x7F 要排在 0x80-0xFF 的后面
{
int shift1 = count[R] - count[R / 2]; // 低半段（正值）移到后面
int shift2 = count[R / 2];
for (int r = 0; r < R / 2; r++)
count[r] += shift1;
for (int r = R / 2; r < R; r++) // 高半段（负值）移到前面
count[r] -= shift2;
}
for (int i = 0; i < n; i++)
{
int c = (a[i] >> BITS_PER_BYTE * d) & MASK;
aux[count[c]++] = a[i];
}
for (int i = 0; i < n; i++)
a[i] = aux[i];
}
} public static void main(String[] args)
{
String[] a = StdIn.readAllStrings();
int n = a.length; int w = a[0].length(); // 检查字符串是否定长
for (int i = 0; i < n; i++)
assert a[i].length() == w : "\n<main> Strings not fixed length.\n"; sort(a, w); for (int i = 0; i < n; i++)
StdOut.println(a[i]);
}
}