▶ 书中第五章部分程序，包括在加上自己补充的代码，字符串高位优先排序（美国国旗排序）
● 美国国旗排序
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stack; public class class01
{
private static final int BITS_PER_BYTE = 8;
private static final int BITS_PER_INT = 32;
private static final int R = 256;
private static final int CUTOFF = 15; private class01() {} public static void sort(String[] a)
{
sortKernel(a, 0, a.length - 1);
} public static void sortKernel(String[] a, int lo, int hi)
{
Stack<Integer> st = new Stack<Integer>();
int[] first = new int[R + 2], next = new int[R + 2];
int d = 0;
for (st.push(lo), st.push(hi), st.push(d); !st.isEmpty();)
{
d = st.pop(); hi = st.pop(); lo = st.pop();
if (hi <= lo + CUTOFF)
{
insertion(a, lo, hi, d);
continue;
}
for (int i = lo; i <= hi; i++) // 以字符串的第 d 位进行统计
first[charAt(a[i], d) + 2]++;
first[0] = lo; // 前部垫起
for (int c = 0; c <= R; c++) // 前缀和与子问题分配
{
first[c + 1] += first[c];
if (c > 0 && first[c + 1] - 1 > first[c]) // 存在至少 2 个第 d 位为 c 的字符串，注意排除 c == 0 的情况
{
st.push(first[c]); // 添加子问题，对第 d 位为 c 的所有字符串关于第 d+1 位进行排序
st.push(first[c + 1] - 1);
st.push(d + 1);
}
}
for (int c = 0; c < R + 2; c++) // 拷贝 first 到 next 中，next 用于搬运字符串过程中的变化索引
next[c] = first[c];
for (int k = lo; k <= hi; k++) // 搬运字符串到指定位置，循环将 a[k] 作为交换的临时位置
{
int c = charAt(a[k], d) + 1; // 取 a[k] 的第 d 位的下一个字符
for (; first[c] > k; c = charAt(a[k], d) + 1) // 只要 c 出现的位置排在 k 后面，就交换 a[k] 和 a[next[c]]，并且 next[c]向后移一个位置
exch(a, k, next[c]++);
next[c]++; // 全部移完了，next[c] 再自增 1，表示 c 开头的索引已经等于 first[c+1]，避免重复排序
}
for (int c = 0; c < R + 2; c++) // 清除 first 和 next
first[c] = next[c] = 0;
}
} private static void insertion(String[] a, int lo, int hi, int d)
{
for (int i = lo; i <= hi; i++)
{
for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)
exch(a, j, j - 1);
}
} private static int charAt(String s, int d)
{
assert d >= 0 && d <= s.length();
if (d == s.length())
return -1;
return s.charAt(d);
} private static void exch(String[] a, int i, int j)
{
String temp = a[i];
a[i] = a[j];
a[j] = temp;
} private static boolean less(String v, String w, int d)
{
assert v.substring(0, d).equals(w.substring(0, d));
for (int i = d; i < Math.min(v.length(), w.length()); i++)
{
if (v.charAt(i) == w.charAt(i))
continue;
return v.charAt(i) < w.charAt(i);
}
return v.length() < w.length();
} public static void sort(int[] a) // 数组排序
{
sortKernel(a, 0, a.length - 1);
} private static void sortKernel(int[] a, int lo, int hi)
{
Stack<Integer> st = new Stack<Integer>();
int[] first = new int[R + 1], next = new int[R + 1];
int mask = R - 1, d = 0;
for (st.push(lo), st.push(hi), st.push(d); !st.isEmpty();)
{
d = st.pop(); hi = st.pop(); lo = st.pop();
if (hi <= lo + CUTOFF)
{
insertion(a, lo, hi, d);
continue;
}
int shift = BITS_PER_INT - BITS_PER_BYTE * (d + 1); // 取从左往右的第 d 字节
for (int i = lo; i <= hi; i++)
first[((a[i] >> shift) & mask) + 1]++;
first[0] = lo;
for (int c = 0; c < R; c++)
{
first[c + 1] += first[c];
if (d < 3 && first[c + 1] - 1 > first[c]) // c > 0 条件改为，当前字节不是最低字节
{
st.push(first[c]);
st.push(first[c + 1] - 1);
st.push(d + 1);
}
}
for (int c = 0; c < R + 1; c++)
next[c] = first[c];
for (int k = lo; k <= hi; k++)
{
int c = (a[k] >> shift) & mask;
for (; first[c] > k; c = (a[k] >> shift) & mask)
exch(a, k, next[c]++);
next[c]++;
}
for (int c = 0; c < R + 1; c++)
first[c] = next[c] = 0;
}
} private static void insertion(int[] a, int lo, int hi, int d)
{
for (int i = lo; i <= hi; i++)
{
for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)
exch(a, j, j - 1);
}
} private static void exch(int[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} private static boolean less(int v, int w, int d)
{
int mask = R - 1;
for (int i = d; i < 4; i++)
{
int shift = BITS_PER_INT - BITS_PER_BYTE * (i + 1);
int a = (v >> shift) & mask, b = (w >> shift) & mask;
if (a == b)
continue;
return a < b;
}
return false;
} public static void main(String[] args)
{
if (args.length > 0 && args[0].equals("int"))
{
int[] a = StdIn.readAllInts();
sort(a); for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
}
else
{
String[] a = StdIn.readAllStrings();
sort(a); for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
}
}
}
● 美国国旗排序 2
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stack; public class class01
{
private static final int R = 256;
private static final int CUTOFF = 15; private class01() {} public static void sort(String[] a)
{
sortKernel(a, 0, a.length - 1);
} public static void sortKernel(String[] a, int lo, int hi)
{
Stack<Integer> st = new Stack<Integer>();
int[] count = new int[R + 1];
int d = 0;
for (st.push(lo), st.push(hi), st.push(d); !st.isEmpty();)
{
d = st.pop(); hi = st.pop(); lo = st.pop();
if (hi <= lo + CUTOFF)
{
insertion(a, lo, hi, d);
continue;
}
for (int i = lo; i <= hi; i++)
count[charAt(a[i], d) + 1]++;
count[0] += lo;
for (int c = 0; c < R; c++)
{
count[c + 1] += count[c]; // count[c] 表示键值不大于 c 的元素个数（相当于字符 c+1 起始位置先前 1 格）
if (c > 0 && count[c + 1] - 1 > count[c])
{
st.push(count[c]);
st.push(count[c + 1] - 1);
st.push(d + 1);
}
}
for (int r = hi; r >= lo; r--) // r 从后向前
{
int c = charAt(a[r], d) + 1;
for (; r >= lo && count[c] - 1 <= r;)
{
if (count[c] - 1 == r)
count[c]--;
r--;
if (r >= lo)
c = charAt(a[r], d) + 1;
}
if (r < lo) // r 已经降到 lo 以下，调整完成
break;
for (count[c]--; count[c] != r; c = charAt(a[r], d) + 1, count[c]--)
exch(a, r, count[c]);
}
}
for (int c = 0; c < R + 1; c++) // 清除 count
count[c] = 0;
} private static void insertion(String[] a, int lo, int hi, int d)
{
for (int i = lo; i <= hi; i++)
{
for (int j = i; j > lo && less(a[j], a[j - 1], d); j--)
exch(a, j, j - 1);
}
} private static int charAt(String s, int d)
{
assert d >= 0 && d <= s.length();
if (d == s.length())
return -1;
return s.charAt(d);
} private static void exch(String[] a, int i, int j)
{
String temp = a[i];
a[i] = a[j];
a[j] = temp;
} private static boolean less(String v, String w, int d)
{
assert v.substring(0, d).equals(w.substring(0, d));
for (int i = d; i < Math.min(v.length(), w.length()); i++)
{
if (v.charAt(i) == w.charAt(i))
continue;
return v.charAt(i) < w.charAt(i);
}
return v.length() < w.length();
} public static void main(String[] args)
{
String[] a = StdIn.readAllStrings();
sort(a); for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
}
}