整个项目都托管在了 github 上：https://github.com/ikesnowy/algorithms-4th-edition-in-csharp
查找更方便的版本见：https://alg4.ikesnowy.com/
这一节内容可能会用到的库文件有 sortapplication，同样在 github 上可以找到。
善用 ctrl + f 查找题目。
在下面这段 string 类型的 compareto() 方法的实现中，第三行对提高运行效率有何帮助？
我要评论public int compareto(string that)
{
if (this == that) return 0; // 这一行
int n = math.min(this.length(), that.length());
for (int i = 0; i < n; i++)
{
if (this.charat(i) < that.charat(i)) return -1;
else if (this.charat(i) > that.charat(i)) return +1;
}
return this.length() - that.length();
}
如果比较的两个 string 引用的是同一个对象，那么就直接返回相等，不必再逐字符比较。
一个例子：
string s = "abcabc"; string p = s; console.writeline(s.compareto(p));
编写一段程序，从标准输入读入一列单词并打印出其中所有由两个单词组成的组合词。
例如，如果输入的单词为 after、thought 和 afterthought，那么 afterthought 就是一个组合词。
将字符串数组 keywords 按照长度排序，于是 keywords[0] 就是最短的字符串。
组合词的最短长度 minlength = 最短字符串的长度 * 2 = keywords[0] * 2。
先找到第一个长度大于等于 minlength 的字符串，下标为 cancombine。
我们从 cancombine 开始，一个个检查是否是组合词。
如果 keywords[cancombine] 是一个组合词，那么它一定是由位于它之前的某两个字符串组合而成的。
组合词的长度一定等于被组合词的长度之和，因此我们可以通过长度快速判断有可能的组合词。
现在题目转化为了如何解决 threesum 问题，即求 a + b = c 型问题，根据 1.4.41 中的解法求解。
keywords[cancombine] 的长度已知，i 从 0 到 cancombine 之间循环，
用二分查找确认 i 到 cancombine 之间有没有符合条件的字符串，注意多个字符串可能长度相等。
using system;
using system.collections.generic;
namespace _2._5._2
{
/*
* 2.5.2
*
* 编写一段程序，从标准输入读入一列单词并打印出其中所有由两个单词组成的组合词。
* 例如，如果输入的单词为 after、thought 和 afterthought，
* 那么 afterthought 就是一个组合词。
*
*/
class program
{
/// <summary>
/// 根据字符串长度进行比较。
/// </summary>
class stringlengthcomparer : icomparer<string>
{
public int compare(string x, string y)
{
return x.length.compareto(y.length);
}
}
/// <summary>
/// 二分查找，返回符合条件的最小下标。
/// </summary>
/// <param name="keys">搜索范围。</param>
/// <param name="length">搜索目标。</param>
/// <param name="lo">起始下标。</param>
/// <param name="hi">终止下标。</param>
/// <returns></returns>
static int binarysearch(string[] keys, int length, int lo, int hi)
{
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (keys[mid].length == length)
{
while (mid >= lo && keys[mid].length == length)
mid--;
return mid + 1;
}
else if (length > keys[mid].length)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
static void main(string[] args)
{
string[] keywords = console.readline().split(' ');
array.sort(keywords, new stringlengthcomparer());
int minlength = keywords[0].length * 2;
// 找到第一个大于 minlength 的字符串
int cancombine = 0;
while (keywords[cancombine].length < minlength &&
cancombine < keywords.length)
cancombine++;
// 依次测试是否可能
while (cancombine < keywords.length)
{
int sum = keywords[cancombine].length;
for (int i = 0; i < cancombine; i++)
{
int start = binarysearch(keywords, sum - keywords[i].length, i, cancombine);
if (start != -1)
{
while (keywords[start].length + keywords[i].length == sum)
{
if (keywords[start] + keywords[i] == keywords[cancombine])
console.writeline(keywords[cancombine] + " = " + keywords[start] + " + " + keywords[i]);
else if (keywords[i] + keywords[start] == keywords[cancombine])
console.writeline(keywords[cancombine] + " = " + keywords[i] + " + " + keywords[start]);
start++;
}
}
}
cancombine++;
}
}
}
}
找出下面这段账户余额 balance 类的实现代码的错误。
为什么 compareto() 方法对 comparable 接口的实现有缺陷？
public class balance implements comparable<balance>
{
private double amount;
public int compareto(banlance that)
{
if (this.amount < that.amount - 0.005) return -1;
if (this.amount > that.amount + 0.005) return +1;
return 0;
}
}
这样会破坏相等的传递性。
例如 a = 0.005, b=0.000, c=-0.005，则 a == b, c == b，但是 a != c。
实现一个方法 string[] dedup(string[] a)，
返回一个有序的 a[]，并删去其中的重复元素。
先排序，然后用书中的代码进行去重。
static string[] dedup(string[] a)
{
if (a.length == 0)
return a;
string[] sorted = new string[a.length];
for (int i = 0; i < a.length; i++)
{
sorted[i] = a[i];
}
array.sort(sorted);
// sorted = sorted.distinct().toarray();
string[] distinct = new string[sorted.length];
distinct[0] = sorted[0];
int j = 1;
for (int i = 1; i < sorted.length; i++)
{
if (sorted[i].compareto(sorted[i - 1]) != 0)
distinct[j++] = sorted[i];
}
return distinct;
}
说明为何选择排序是不稳定的？
因为选择排序会交换不相邻的元素。
例如：
b1 b2 a a b2 b1
此时 b1 和 b2 的相对位置被改变，如果将交换限定在相邻元素之间（插入排序）。
b1 b2 a b1 a b2 a b2 b2
此时排序就是稳定的了。
用递归实现 select()。
非递归官网实现见：https://algs4.cs.princeton.edu/23quicksort/quickpedantic.java.html
原本是和快速排序一块介绍的，将数组重新排列，使得 a[k] 正好是第 k 小的元素，k 从 0 开始。
具体思路类似于二分查找，
先切分，如果切分位置小于 k，那么在右半部分继续切分，否则在左半部分继续切分。
直到切分位置正好等于 k，直接返回 a[k] 。
/// <summary>
/// 使 a[k] 变为第 k 小的数，k 从 0 开始。
/// a[0] ~ a[k-1] 都小于等于 a[k], a[k+1]~a[n-1] 都大于等于 a[k]
/// </summary>
/// <typeparam name="t">元素类型。</typeparam>
/// <param name="a">需要调整的数组。</param>
/// <param name="k">序号。</param>
/// <param name="lo">起始下标。</param>
/// <param name="hi">终止下标。</param>
/// <returns></returns>
static t select<t>(t[] a, int k, int lo, int hi) where t : icomparable<t>
{
if (k > a.length || k < 0)
throw new argumentoutofrangeexception("select out of bound");
if (lo >= hi)
return a[lo];
int i = partition(a, lo, hi);
if (i > k)
return select(a, k, lo, i - 1);
else if (i < k)
return select(a, k, i + 1, hi);
else
return a[i];
}
用 select() 找出 n 个元素中的最小值平均大约需要多少次比较？
参考书中给出的快速排序性能分析方法（中文版 p186，英文版 p293）。
设 $ c_n $ 代表找出 $ n $ 个元素中的最小值所需要的比较次数。
一次切分需要 $ n+1 $ 次比较，下一侧的元素个数从 $ 0 $ 到 $ n-1 $ 都有可能，
于是根据全概率公式，有：
\[
\begin{eqnarray*}
c_n&=&\frac {1}{n} (n+1) +\frac{1}{n} (n+1+c_1)+ \cdots + \frac{1}{n}(n+1+c_{n-1}) \\
c_n&=&n+1+\frac{1}{n}(c_1+c_2+\cdots+c_{n-1}) \\
nc_n&=&n(n+1)+(c_1+c_2+\cdots+c_{n-1}) \\
nc_n-(n-1)c_{n-1}&=&2n+c_{n-1} \\
nc_n&=&2n+nc_{n-1} \\
c_n&=&2+c_{n-1} \\
c_n &=& c_1+2(n-1) \\
c_n &=& 2n-2 < 2n
\end{eqnarray*}
\]
测试结果符合我们的预期。
附加：找出第 $ k $ 小的数平均需要的比较次数。
类似的方法也在计算快速排序的平均比较次数时使用，见题 2.3.14。
首先和快速排序类似，select 方法的所有元素比较都发生在切分过程中。
接下来考虑第 $ i $ 小和第 $ j $ 小的元素（$ x_i $ ，$ x_j $），
当枢轴选为 $ x_i $ 或 $ x_j $ 时，它们会发生比较；
如果枢轴选为 $ x_i $ 和 $ x_j $ 之间的元素，那么它们会被切分到两侧，不可能发生比较；
如果枢轴选为小于 $ x_i $ 或大于 $ x_j $ 的元素，它们会被切分到同一侧，进入下次切分。
但要注意的是，select 只会对切分的一侧进行再切分，另一侧会被抛弃（快速排序则是两侧都会再切分）。
因此我们需要将第 $ k $ 小的数 $ x_k $ 纳入考虑。
如果 $ x_k>x_j>x_i $ ，且枢轴选了 $ x_k $ 到 $ x_j $ 之间的元素，切分后 $ x_i $ 和 $ x_j $ 会被一起抛弃，不发生比较。
如果 $ x_j > x_k > x_i $ ，枢轴的选择情况和快速排序一致。
如果 $ x_j > x_i > x_k $ ，且枢轴选了 $ x_i $ 到 $ x_k $ 之间的元素，切分后 $ x_i $ 和 $ x_j $ 会被一起抛弃，不发生比较。
综上我们可以得到 $ x_i $ 和 $ x_j $ 之间发生比较的概率 $ \frac{2}{\max(j-i+1, k-i+1,j-k+1)} $ 。
我们利用线性规划的知识把最大值函数的区域画出来，如下图所示：
对蓝色区域积分得：
\[
\begin{eqnarray*}
&&\int_{0}^{k} dj \int_{0}^{j} \frac{2}{j-k+1}\ di \\
&=& 2 \int_{0}^{k} \frac{j}{j-k+1} \ dj \\
&<& 2 k
\end{eqnarray*}
\]
对红色区域积分得：
\[
\begin {eqnarray*}
&& \int_{k}^{n} di \int_{i}^{n} \frac{2}{k-i+1} dj \\
&=& 2\int_{k}^{n} \frac{n-i}{k-i+1} di \\
&<& 2(n-k)
\end {eqnarray*}
\]
对绿色区域积分得：
\[
\begin{eqnarray*}
&& \int_{0}^{k}di\int_{k}^{n} \frac{2}{j-i+1} dj \\
&<& \int_{0}^{k}di\int_{k}^{n} \frac{2}{j-i} dj \\
&=& 2\int_{0}^{k} \ln (n-i) di - 2\int_{0}^{k} \ln(k-i)di \\
&=& 2i\ln(n-i) \bigg|_{0}^{k} + 2\int_{0}^{k}\frac{i}{n-i} di -
\left[ i\ln(k-i) \bigg|_{0}^{k} + 2\int_{0}^{k} \frac{i}{k-i} di \right] \\
&=& 2k\ln(n-k)+2\int_{0}^{k}\frac{n}{n-i}-1 \ di -2\int_{0}^{k} \frac{k}{k-i}-1 \ di \\
&=& 2k\ln(n-k)+2\int_{0}^{k}\frac{n}{n-i} \ di -2k - 2\int_{0}^{k} \frac{k}{k-i} \ di +2k \\
&=& 2k\ln(n-k) -2n\ln(n-i) \bigg|_{0}^{k} +2k\ln(k-i)\bigg|_{0}^{k} \\
&=& 2k\ln(n-k)-2n\ln(n-k)+2n\ln n -2k\ln k
\end{eqnarray*}
\]
全部相加得到：
\[
\begin{eqnarray*}
&& 2k+2(n-k)+2k\ln(n-k)-2n\ln(n-k)+2n\ln n -2k\ln k \\
&=& 2n + 2k\ln(n-k)-2n\ln(n-k)+2n\ln n -2k\ln k \\
&=& 2n + 2k\ln(n-k)-2n\ln(n-k)+2n\ln n-2k\ln k +2k\ln n-2k\ln n \\
&=& 2n + 2k\ln n-2k\ln k+2n\ln n-2n\ln(n-k) - 2k\ln n + 2k\ln(n-k) \\
&=& 2n + 2k\ln \left(\frac{n}{k} \right)+2n\ln\left(\frac{n}{n-k} \right) - 2k\ln\left(\frac{n}{n-k} \right) \\
&=& 2n+2k\ln\left(\frac{n}{k}\right)+2(n-k)\ln\left(\frac{n}{n-k} \right)
\end{eqnarray*}
\]
于是得到了命题 u 中的结果（中文版 p221，英文版 p347）。
blum-style analysis of quickselect
编写一段程序 frequency，
从标准输入读取一列字符串并按照字符串出现频率由高到低的顺序打印出每个字符串及其出现次数。
官网实现见：https://algs4.cs.princeton.edu/25applications/frequency.java.html
用到的数据来自（右键另存为）：https://introcs.cs.princeton.edu/java/data/tale.txt
先把所有单词读入，然后排序，一样的单词会被放在一起，
接下来遍历一遍记录每个单词出现的次数。
然后按照频率排序，倒序输出即可。
定义了一个嵌套类 record 来记录单词及出现次数，实现的比较器按照出现次数排序。
class record : icomparable<record>
{
public string key { get; set; } // 单词
public int value { get; set; } // 频率
public record(string key, int value)
{
this.key = key;
this.value = value;
}
public int compareto(record other)
{
return this.value.compareto(other.value);
}
}
测试结果：
using system;
using system.io;
namespace _2._5._8
{
class program
{
class record : icomparable<record>
{
public string key { get; set; } // 单词
public int value { get; set; } // 频率
public record(string key, int value)
{
this.key = key;
this.value = value;
}
public int compareto(record other)
{
return this.value.compareto(other.value);
}
}
static void main(string[] args)
{
string filename = "tale.txt";
streamreader sr = new streamreader(file.openread(filename));
string[] a = sr.readtoend().split(new char[] { ' ', '\n', '\r' }, stringsplitoptions.removeemptyentries);
array.sort(a);
record[] records = new record[a.length];
string word = a[0];
int freq = 1;
int m = 0;
for (int i = 0; i < a.length; i++)
{
if (!a[i].equals(word))
{
records[m++] = new record(word, freq);
word = a[i];
freq = 0;
}
freq++;
}
records[m++] = new record(word, freq);
array.sort(records, 0, m);
// 只显示频率为前 1% 的单词
for (int i = m - 1; i >= m * 0.99; i--)
console.writeline(records[i].value + " " + records[i].key);
}
}
}
为将右侧所示的数据排序编写一个新的数据类型。
右侧给出的是道琼斯指数，官方数据（右键另存为）：dji
设计一个类保存日期和交易量，然后按照交易量排序即可。
/// <summary>
/// 道琼斯指数。
/// </summary>
class djia : icomparable<djia>
{
public string date { get; set; }
public long volume { get; set; }
public djia(string date, long vol)
{
this.date = date;
this.volume = vol;
}
public int compareto(djia other)
{
return this.volume.compareto(other.volume);
}
}
创建一个数据类型 version 来表示软件的版本，例如 155.1.1、155.10.1、155.10.2。
为它实现 comparable 接口，其中 115.1.1 的版本低于 115.10.1。
用一个 int 数组来保存版本号，按顺序进行比较。
如果两个版本号不等长且前缀相同，那么较长的版本号比较高，例如：1.2.1 和 1.2。
using system;
namespace _2._5._10
{
/// <summary>
/// 版本号。
/// </summary>
class version : icomparable<version>
{
private int[] versionnumber;
public version(string version)
{
string[] versions = version.split('.');
this.versionnumber = new int[versions.length];
for (int i = 0; i < versions.length; i++)
{
this.versionnumber[i] = int.parse(versions[i]);
}
}
public int compareto(version other)
{
for (int i = 0; i < this.versionnumber.length && i < other.versionnumber.length; i++)
{
if (this.versionnumber[i].compareto(other.versionnumber[i]) != 0)
return this.versionnumber[i].compareto(other.versionnumber[i]);
}
return this.versionnumber.length.compareto(other.versionnumber.length);
}
public override string tostring()
{
string result = "";
for (int i = 0; i < this.versionnumber.length - 1; i++)
{
result += this.versionnumber[i] + ".";
}
result += this.versionnumber[this.versionnumber.length - 1].tostring();
return result;
}
}
}
描述排序结果的一种方法是创建一个保存 0 到 a.length - 1 的排列 p[]，
使得 p[i] 的值为 a[i] 元素的最终位置。
用这种方法描述插入排序、选择排序、希尔排序、归并排序、快速排序和堆排序
对一个含有 7 个相同元素的数组的排序结果。
结果如下，其中快速排序去掉了一开始打乱数组的步骤：
只有快速排序和堆排序会进行交换，剩下四种排序都不会进行交换。
插入排序在排序元素完全相同的数组时只会进行一次遍历，不会交换。
选择排序第 i 次找到的最小值就是 a[i] ，只会让 a[i] 和 a[i] 交换，不会影响顺序。
希尔排序和插入排序类似，每轮排序都不会进行交换。
归并排序是稳定的，就本例而言，只会从左到右依次归并，不会发生顺序变化。
快速排序在遇到相同元素时会交换，因此顺序会发生变化，且每次都是对半切分。
堆排序在删除最大元素时会将第一个元素和最后一个元素交换，使元素顺序发生变化。
using system;
using sortapplication;
namespace _2._5._11
{
class program
{
/// <summary>
/// 用来排序的元素，记录有自己的初始下标。
/// </summary>
/// <typeparam name="t"></typeparam>
class item<t> : icomparable<item<t>> where t : icomparable<t>
{
public int index;
public t key;
public item(int index, t key)
{
this.index = index;
this.key = key;
}
public int compareto(item<t> other)
{
return this.key.compareto(other.key);
}
}
static void main(string[] args)
{
// 插入排序
console.writeline("insertion sort");
test(new insertionsort(), 7, 1);
// 选择排序
console.writeline("selection sort");
test(new selectionsort(), 7, 1);
// 希尔排序
console.writeline("shell sort");
test(new shellsort(), 7, 1);
// 归并排序
console.writeline("merge sort");
test(new mergesort(), 7, 1);
// 快速排序
console.writeline("quick sort");
quicksortanalyze quick = new quicksortanalyze
{
needshuffle = false,
needpath = false
};
test(quick, 7, 1);
// 堆排序
console.writeline("heap sort");
item<int>[] array = new item<int>[7];
for (int i = 0; i < 7; i++)
array[i] = new item<int>(i, 1);
heap.sort(array);
for (int i = 0; i < 7; i++)
console.write(array[i].index + " ");
console.writeline();
}
static void test(basesort sort, int n, int constant)
{
item<int>[] array = new item<int>[n];
for (int i = 0; i < n; i++)
array[i] = new item<int>(i, constant);
sort.sort(array);
for (int i = 0; i < n; i++)
console.write(array[i].index + " ");
console.writeline();
}
}
}
调度。
编写一段程序 spt.java，从标准输入中读取任务的名称和所需的运行时间，
用 2.5.4.3 节所述的最短处理时间优先的原则打印出一份调度计划，使得任务完成的平均时间最小。
官方解答：https://algs4.cs.princeton.edu/25applications/spt.java.html
把任务按照处理时间升序排序即可。
建立 job 类，保存任务的名称和处理时间，并实现了 iconparable<job> 接口。
class job : icomparable<job>
{
public string name;
public double time;
public job(string name, double time)
{
this.name = name;
this.time = time;
}
public int compareto(job other)
{
return this.time.compareto(other.time);
}
}
using system;
namespace _2._5._12
{
class program
{
class job : icomparable<job>
{
public string name;
public double time;
public job(string name, double time)
{
this.name = name;
this.time = time;
}
public int compareto(job other)
{
return this.time.compareto(other.time);
}
}
static void main(string[] args)
{
// 官方解答：https://algs4.cs.princeton.edu/25applications/spt.java.html
int n = int.parse(console.readline());
job[] jobs = new job[n];
for (int i = 0; i < n; i++)
{
string[] input = console.readline().split(' ');
jobs[i] = new job(input[0], double.parse(input[1]));
}
array.sort(jobs);
for (int i = 0; i < jobs.length; i++)
{
console.writeline(jobs[i].name + " " + jobs[i].time);
}
}
}
}
负载均衡。
编写一段程序 lpt.java，接受一个整数 m 作为命令行参数，
从标准输入中读取任务的名称和所需的运行时间，
用 2.5.4.3 所述的最长处理时间优先原则打印出一份调度计划，
将所有任务分配给 m 个处理器并使得所有任务完成所需的总时间最少。
官方解答见：https://algs4.cs.princeton.edu/25applications/lpt.java.html
使用上题的 job 类，在本题建立 processor 类来代表处理器，定义如下：
class processor : icomparable<processor>
{
private list<job> jobs = new list<job>();
private double busytime = 0;
public processor() { }
public void add(job job)
{
this.jobs.add(job);
this.busytime += job.time;
}
public int compareto(processor other)
{
return this.busytime.compareto(other.busytime);
}
public override string tostring()
{
stringbuilder sb = new stringbuilder();
job[] nowlist = this.jobs.toarray();
for (int i = 0; i < nowlist.length; i++)
{
sb.appendline(nowlist[i].name + " " + nowlist[i].time);
}
return sb.tostring();
}
}
按照读入所有的任务并排序，再将所有的处理器放进一个最小堆里。
从最小堆取出任务最轻的处理器，按取耗时最长的任务分配给它，再将它放回最小堆中。
最后依次打印处理器的任务分配即可。
using system;
using system.collections.generic;
using system.text;
using sortapplication;
namespace _2._5._13
{
class program
{
class job : icomparable<job>
{
public string name;
public double time;
public job(string name, double time)
{
this.name = name;
this.time = time;
}
public int compareto(job other)
{
return this.time.compareto(other.time);
}
}
class processor : icomparable<processor>
{
private list<job> jobs = new list<job>();
private double busytime = 0;
public processor() { }
public void add(job job)
{
this.jobs.add(job);
this.busytime += job.time;
}
public int compareto(processor other)
{
return this.busytime.compareto(other.busytime);
}
public override string tostring()
{
stringbuilder sb = new stringbuilder();
job[] nowlist = this.jobs.toarray();
for (int i = 0; i < nowlist.length; i++)
{
sb.appendline(nowlist[i].name + " " + nowlist[i].time);
}
return sb.tostring();
}
}
static void main(string[] args)
{
int processornum = int.parse(console.readline());
int jobnum = int.parse(console.readline());
job[] jobs = new job[jobnum];
for (int i = 0; i < jobnum; i++)
{
string[] jobdesc = console.readline().split(' ');
jobs[i] = new job(jobdesc[0], double.parse(jobdesc[1]));
}
array.sort(jobs);
minpq<processor> processors = new minpq<processor>(processornum);
for (int i = 0; i < processornum; i++)
{
processors.insert(new processor());
}
for (int i = jobs.length - 1; i >= 0; i--)
{
processor min = processors.delmin();
min.add(jobs[i]);
processors.insert(min);
}
while (!processors.isempty())
{
console.writeline(processors.delmin());
}
}
}
}
逆域名排序。
为域名编写一个数据类型 domain 并为它实现一个 compareto() 方法，使之能够按照逆向的域名排序。
例如，域名 cs.princeton.edu 的逆是 edu.princeton.cs。
这在网络日志处理时很有用。
提示：使用s.split(".") 将域名用点分为若干部分。
编写一个 domain 的用例，从标准输入读取域名并将他们按照逆域名有序地打印出来。
官方解答：https://algs4.cs.princeton.edu/25applications/domain.java.html
按照逆域名排序，例如输入的是 com.google 和 com.apple ，
比较的时候是按照 google.com 和 apple.com 进行比较的。
排序结果自然是 apple.com, google.com。
编写的 domain 类，compareto() 中是按照倒序进行比较的。
using system;
using system.text;
namespace _2._5._14
{
/// <summary>
/// 域名类。
/// </summary>
class domain : icomparable<domain>
{
private string[] fields;
private int n;
/// <summary>
/// 构造一个域名。
/// </summary>
/// <param name="url">域名的 url。</param>
public domain(string url)
{
this.fields = url.split('.');
this.n = this.fields.length;
}
public int compareto(domain other)
{
int minlength = math.min(this.n, other.n);
for (int i = 0; i < minlength; i++)
{
int c = this.fields[minlength - i - 1].compareto(other.fields[minlength - i - 1]);
if (c != 0)
return c;
}
return this.n.compareto(other.n);
}
public override string tostring()
{
stringbuilder sb = new stringbuilder();
for (int i = 0; i < this.fields.length; i++)
{
if (i != 0)
sb.append('.');
sb.append(this.fields[i]);
}
return sb.tostring();
}
}
}
using system;
namespace _2._5._14
{
class program
{
static void main(string[] args)
{
domain[] domains = new domain[5];
domains[0] = new domain("edu.princeton.cs");
domains[1] = new domain("edu.princeton.ee");
domains[2] = new domain("com.google");
domains[3] = new domain("edu.princeton");
domains[4] = new domain("com.apple");
array.sort(domains);
for (int i = 0; i < domains.length; i++)
{
console.writeline(domains[i]);
}
}
}
}
垃圾邮件大战。
在非法垃圾邮件之战的伊始，
你有一大串来自各个域名（也就是电子邮件地址中@符号后面的部分）的电子邮件地址。
为了更好的伪造回信地址，你应该总是从相同的域中向目标用户发送邮件。
例如，从 wayne@cs.pinceton.edu 向 rs@cs.princeton.edu 发送垃圾邮件就很不错。
你会如何处理这份电子邮件列表来高效的完成这个任务呢？
利用上一题的逆域名排序将域名相同的电子邮件分在一起。
using system;
namespace _2._5._15
{
class program
{
static void main(string[] args)
{
// 利用上一题的逆域名排序，将相同的域名放在一起。
domain[] emails = new domain[5];
emails[0] = new domain("wayne@cs.princeton.edu");
emails[1] = new domain("windy@apple.com");
emails[2] = new domain("rs@cs.princeton.edu");
emails[3] = new domain("ike@ee.princeton.edu");
emails[4] = new domain("admin@princeton.edu");
array.sort(emails);
for (int i = 0; i < emails.length; i++)
{
console.writeline(emails[i]);
}
}
}
}
公正的选举。
为了避免对名字排在字母表靠后的候选人的偏见，
加州在 2003 年的州长选举中将所有候选人按照以下字母顺序排列：
r w q o j m v a h b s g z x n t c i e k u p d y f l。
创建一个遵守这种顺序的数据类型并编写一个用例 california，
在它的静态方法 main() 中将字符串按照这种方式排序。
假设所有字符串都是大写的。
官方解答：https://algs4.cs.princeton.edu/25applications/california.java.html
数据来源：https://introcs.cs.princeton.edu/java/data/california-gov.txt
建立一个 string 的比较器，按照题目给定的顺序比较。
private class candidatecomparer : icomparer<string>
{
private static readonly string order = "rwqojmvahbsgzxntciekupdyfl";
public int compare(string x, string y)
{
int n = math.min(x.length, y.length);
for (int i = 0; i < n; i++)
{
int a = order.indexof(x[i]);
int b = order.indexof(y[i]);
if (a != b)
return a.compareto(b);
}
return x.length.compareto(y.length);
}
}
using system;
using system.io;
using system.collections.generic;
namespace _2._5._16
{
class program
{
// 官方解答：https://algs4.cs.princeton.edu/25applications/california.java.html
private class candidatecomparer : icomparer<string>
{
private static readonly string order = "rwqojmvahbsgzxntciekupdyfl";
public int compare(string x, string y)
{
int n = math.min(x.length, y.length);
for (int i = 0; i < n; i++)
{
int a = order.indexof(x[i]);
int b = order.indexof(y[i]);
if (a != b)
return a.compareto(b);
}
return x.length.compareto(y.length);
}
}
static void main(string[] args)
{
// 数据来源：https://introcs.cs.princeton.edu/java/data/california-gov.txt
streamreader sr = new streamreader(file.openread("california-gov.txt"));
string[] names =
sr.readtoend()
.toupper()
.split
(new char[] { '\n', '\r' },
stringsplitoptions.removeemptyentries);
array.sort(names, new candidatecomparer());
for (int i = 0; i < names.length; i++)
{
console.writeline(names[i]);
}
}
}
}
检测稳定性。
扩展练习 2.1.16 中的 check() 方法，对指定数组调用 sort()，
如果排序结果是稳定的则返回 true，否则返回 false。
不要假设 sort() 只会使用 exch() 移动数据。
用一个 wrapper 类包装准备排序的元素，在排序前同时记录元素的内容和下标。
随后对 wrapper 数组排序，相同的元素会被放在一起，检查它们的下标是否是递增的。
如果不是递增的，则排序算法就是不稳定的；否则排序算法就有可能是稳定的。
（不稳定的排序算法也可能不改变相同元素的相对位置，比如用选择排序对有序数组排序）
using system;
using sortapplication;
namespace _2._5._17
{
class program
{
class wrapper<t> : icomparable<wrapper<t>> where t : icomparable<t>
{
public int index;
public t key;
public wrapper(int index, t elements)
{
this.index = index;
this.key = elements;
}
public int compareto(wrapper<t> other)
{
return this.key.compareto(other.key);
}
}
static void main(string[] args)
{
int[] data = new int[] { 7, 7, 4, 8, 8, 5, 1, 7, 7 };
mergesort merge = new mergesort();
insertionsort insertion = new insertionsort();
shellsort shell = new shellsort();
selectionsort selection = new selectionsort();
quicksort quick = new quicksort();
console.writeline("merge sort: " + checkstability(data, merge));
console.writeline("insertion sort: " + checkstability(data, insertion));
console.writeline("shell sort: " + checkstability(data, shell));
console.writeline("selection sort: " + checkstability(data, selection));
console.writeline("quick sort: " + checkstability(data, quick));
}
static bool checkstability<t>(t[] data, basesort sort) where t : icomparable<t>
{
wrapper<t>[] items = new wrapper<t>[data.length];
for (int i = 0; i < data.length; i++)
items[i] = new wrapper<t>(i, data[i]);
sort.sort(items);
int index = 0;
while (index < data.length - 1)
{
while (index < data.length - 1 && items[index].key.equals(items[index + 1].key))
{
if (items[index].index > items[index + 1].index)
return false;
index++;
}
index++;
}
return true;
}
}
}
强制稳定。
编写一段能够将任意排序方法变得稳定的封装代码，
创建一种新的数据类型作为键，将键的原始索引保存在其中，
并在调用 sort() 之后再恢复原始的键。
用和上题一样的 wrapper 类进行排序。
排序之后，相同的元素会被放在一起，形成一个个子数组。
根据事先保存的原始下标对它们进行排序，即可将不稳定的排序稳定化。
结果：
using system;
using sortapplication;
namespace _2._5._18
{
class program
{
class wrapper<t> : icomparable<wrapper<t>> where t : icomparable<t>
{
public int index;
public t key;
public wrapper(int index, t elements)
{
this.index = index;
this.key = elements;
}
public int compareto(wrapper<t> other)
{
return this.key.compareto(other.key);
}
}
static void main(string[] args)
{
int[] data = new int[] { 5, 7, 3, 4, 7, 3, 6, 3, 3 };
quicksort quick = new quicksort();
shellsort shell = new shellsort();
console.writeline("quick sort");
stabilize(data, quick);
console.writeline();
console.writeline("shell sort");
stabilize(data, shell);
}
static void stabilize<t>(t[] data, basesort sort) where t : icomparable<t>
{
wrapper<t>[] items = new wrapper<t>[data.length];
for (int i = 0; i < data.length; i++)
{
items[i] = new wrapper<t>(i, data[i]);
}
sort.sort(items);
console.write("index:\t");
for (int i = 0; i < items.length; i++)
{
console.write(items[i].index + " ");
}
console.writeline();
console.write("elem:\t");
for (int i = 0; i < items.length; i++)
{
console.write(items[i].key + " ");
}
console.writeline();
console.writeline();
int index = 0;
while (index < items.length - 1)
{
while (index < items.length - 1 &&
items[index].key.equals(items[index + 1].key))
{
// 插入排序
for (int j = index + 1; j > 0 && items[j].index < items[j - 1].index; j--)
{
if (!items[j].key.equals(items[j - 1].key))
break;
wrapper<t> temp = items[j];
items[j] = items[j - 1];
items[j - 1] = temp;
}
index++;
}
index++;
}
console.write("index:\t");
for (int i = 0; i < items.length; i++)
{
console.write(items[i].index + " ");
}
console.writeline();
console.write("elem:\t");
for (int i = 0; i < items.length; i++)
{
console.write(items[i].key + " ");
}
console.writeline();
}
}
}
kendall tau 距离。
编写一段程序 kendalltau.java ，
在线性对数时间内计算两组排列之间的 kendall tau 距离。
官方解答：
kendall tau：https://algs4.cs.princeton.edu/25applications/kendalltau.java.html
inversion：https://algs4.cs.princeton.edu/22mergesort/inversions.java.html
由书中 2.5.3.2 节得，两个数组之间的 kendall tau 距离即为两数组之间顺序不同的数对数目。
如果能够把其中一个数组变成标准排列（即 1,2,3,4... 这样的数组），
那么此时 kendall tau 距离就等于另一个数组中的逆序对数量。
现在我们来解决如何把一个数组 a 变成标准排列的方法。
也就是找到函数 $ f(x) $，使得 $ f(a[i])=i $ ，这样的函数其实就是数组 a 的逆数组。
如下图所示，逆数组 ainv 即为满足 ainv[a[i]] = i 的数组。
获得逆数组之后，对另一个数组 b 做同样的变换，令数组 bnew[i] = ainv[b[i]] 。
即 ainv[a[i]] = i, ainv[b[i]] = bnew[i] 。
于是问题转化为了 bnew 和标准排列之间的 kendall tau 距离，即 bnew 的逆序对数量。
逆序对数量的求法见题 2.2.19。
using system;
namespace _2._5._19
{
class program
{
static void main(string[] args)
{
// 官方解答：
// https://algs4.cs.princeton.edu/25applications/kendalltau.java.html
// https://algs4.cs.princeton.edu/22mergesort/inversions.java.html
int[] testa = { 0, 3, 1, 6, 2, 5, 4 };
int[] testb = { 1, 0, 3, 6, 4, 2, 5 };
console.writeline(distance(testa, testb));
}
public static long distance(int[] a, int[] b)
{
if (a.length != b.length)
throw new argumentexception("array dimensions disagree");
int n = a.length;
int[] ainv = new int[n];
for (int i = 0; i < n; i++)
{
ainv[a[i]] = i;
}
int[] bnew = new int[n];
for (int i = 0; i < n; i++)
{
bnew[i] = ainv[b[i]];
}
inversions inversions = new inversions();
inversions.count(bnew);
return inversions.counter;
}
}
}
空闲时间。
假设有一台计算机能够并行处理 n 个任务。
编写一段程序并给定一系列任务的起始时间和结束时间，
找出这台机器最长的空闲时间和最长的繁忙时间。
我们按照事件来处理即可，每个事件包含任务名，时间和开始/结束标志。
随后按照时间从小到大排序，遍历数组即可。
设开始的时候机器空闲，设置计数器，作为当前正在运行的任务数量。
如果计数器加一之前计数器为 0，说明空闲状态结束，记录并更新空闲时间，当前时间为忙碌开始的时间。
如果计数器减一之后计数器为 0，说明忙碌状态结束，记录并更新忙碌时间，当前时间为空闲开始的时间。
测试结果：
using system;
namespace _2._5._20
{
class program
{
/// <summary>
/// 任务变化事件。
/// </summary>
class jobevent : icomparable<jobevent>
{
public string jobname;
public int time;
public bool isfinished = false; // false = 开始，true = 结束
public int compareto(jobevent other)
{
return this.time.compareto(other.time);
}
}
static void main(string[] args)
{
// 输入格式： jobname 15:02 17:02
int nowrunning = 0; // 正在运行的程序数量
int maxidle = 0;
int maxbusy = 0;
int items = int.parse(console.readline());
jobevent[] jobs = new jobevent[items * 2];
for (int i = 0; i < jobs.length; i += 2)
{
jobs[i] = new jobevent();
jobs[i + 1] = new jobevent();
jobs[i].isfinished = false; // 开始事件
jobs[i + 1].isfinished = true; // 停止事件
string[] record = console.readline().split(new char[] { ' ', ':' }, stringsplitoptions.removeemptyentries);
jobs[i].jobname = record[0];
jobs[i + 1].jobname = record[0];
jobs[i].time = int.parse(record[1]) * 60 + int.parse(record[2]);
jobs[i + 1].time = int.parse(record[3]) * 60 + int.parse(record[4]);
}
array.sort(jobs);
// 事件处理
int idlestart = 0;
int busystart = 0;
for (int i = 0; i < jobs.length; i++)
{
// 启动事件
if (!jobs[i].isfinished)
{
// 空闲状态结束
if (nowrunning == 0)
{
int idle = jobs[i].time - idlestart;
if (idle > maxidle)
maxidle = idle;
// 开始忙碌
busystart = jobs[i].time;
}
nowrunning++;
}
else
{
nowrunning--;
// 忙碌状态结束
if (nowrunning == 0)
{
int busy = jobs[i].time - busystart;
if (busy > maxbusy)
maxbusy = busy;
// 开始空闲
idlestart = jobs[i].time;
}
}
}
console.writeline("max idle: " + maxidle);
console.writeline("max busy: " + maxbusy);
}
}
}
多维排序。
编写一个 vector 数据类型并将 d 维整型向量排序。
排序方法是先按照一维数字排序，一维数字相同的向量则按照二维数字排序，
再相同的向量则按照三维数字排序，如此这般。
与之前的版本号比较十分类似，对数组进行包装，然后按照次序依次比较即可。
using system;
using system.text;
namespace _2._5._21
{
class vector : icomparable<vector>
{
private int[] data;
public int length { get; set; }
public vector(int[] data)
{
this.data = data;
this.length = data.length;
}
public int compareto(vector other)
{
int maxn = math.max(this.length, other.length);
for (int i = 0; i < maxn; i++)
{
int comp = this.data[i].compareto(other.data[i]);
if (comp != 0)
return comp;
}
return this.length.compareto(other.length);
}
public override string tostring()
{
stringbuilder sb = new stringbuilder();
for (int i = 0; i < this.length; i++)
{
if (i != 0)
sb.append(' ');
sb.append(this.data[i]);
}
return sb.tostring();
}
}
}
股票交易。
投资者堆一只股票的买卖交易都发布在电子交易市场中。
他们会指定最高买入价和最低卖出价，以及在该价位买卖的笔数。
编写一段程序，用优先队列来匹配买家和卖家并用模拟数据进行测试。
可以使用两个优先队列，一个用于买家一个用于卖家，
当一方的报价能够和另一方的一份或多份报价匹配时就进行交易。
建立最小堆和最大堆，最小堆保存卖家的报价，最大堆保存买家的报价。
如果最小堆中的最低卖出价低于最大堆的最高买入价，交易达成，交易份额较大的一方需要重新回到堆内。
测试结果：
using system;
using sortapplication;
namespace _2._5._22
{
class program
{
class ticket : icomparable<ticket>
{
public double price;
public int share;
public int compareto(ticket other)
{
return this.price.compareto(other.price);
}
}
static void main(string[] args)
{
// 输入格式： buy 20.05 100
maxpq<ticket> buyer = new maxpq<ticket>();
minpq<ticket> seller = new minpq<ticket>();
int n = int.parse(console.readline());
for (int i = 0; i < n; i++)
{
ticket ticket = new ticket();
string[] item = console.readline().split(' ');
ticket.price = double.parse(item[1]);
ticket.share = int.parse(item[2]);
if (item[0] == "buy")
buyer.insert(ticket);
else
seller.insert(ticket);
}
while (!buyer.isempty() && !seller.isempty())
{
if (buyer.max().price < seller.min().price)
break;
ticket buy = buyer.delmax();
ticket sell = seller.delmin();
console.write("sell $" + sell.price + " * " + sell.share);
if (buy.share > sell.share)
{
console.writeline(" -> " + sell.share + " -> $" + buy.price + " * " + buy.share + " buy");
buy.share -= sell.share;
buyer.insert(buy);
}
else if (buy.share < sell.share)
{
sell.share -= buy.share;
seller.insert(sell);
console.writeline(" -> " + buy.share + " -> $" + buy.price + " * " + buy.share + " buy");
}
else
{
console.writeline(" -> " + sell.share + " -> $" + buy.price + " * " + buy.share + " buy");
}
}
}
}
}
选择的取样：实验使用取样来改进 select() 函数的想法。
提示：使用中位数可能并不总是有效。
这里我们使用 floyd-rivest 算法进行优化，大致思想是：
我们期望第 $ k $ 大的元素位于 a[k] 附近，因此优先对 a[k] 附近的区域进行选择。
每次切分时枢轴都选择 a[k]，先递归对样本区域选择，再对整个数组进行选择。
运行示意图：
测试结果：
/// <summary>
/// floyd–rivest 方法优化，令 a[k] 变成第 k 小的元素。
/// </summary>
/// <typeparam name="t">元素类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
/// <param name="k">序号</param>
/// <returns></returns>
static t select<t>(t[] a, int lo, int hi, int k) where t : icomparable<t>
{
if (k < 0 || k > a.length)
throw new indexoutofrangeexception("select elements out of bounds");
while (hi > lo)
{
if (hi - lo > 600)
{
int n = hi - lo + 1;
int i = k - lo + 1;
int z = (int)math.log(n);
int s = (int)(math.exp(2 * z / 3) / 2);
int sd = (int)math.sqrt(z * s * (n - s) / n) * math.sign(i - n / 2) / 2;
int newlo = math.max(lo, k - i * s / n + sd);
int newhi = math.min(hi, k + (n - i) * s / n + sd);
select(a, newlo, newhi, k);
}
exch(a, lo, k);
int j = partition(a, lo, hi);
if (j > k)
hi = j - 1;
else if (j < k)
lo = j + 1;
else
return a[j];
}
return a[lo];
}
floyd–rivest algorithm - wikipedia
稳定的优先队列。
实现一个稳定的优先队列（将重复的元素按照它们被插入的顺序返回）。
官方解答：https://algs4.cs.princeton.edu/25applications/stableminpq.java.html
在元素插入的同时记录插入顺序，比较的时候把插入顺序也纳入比较。
对于值一样的元素，插入顺序在前的的元素比较小。
交换的时候需要同时交换插入次序。
using system;
using system.collections;
using system.collections.generic;
namespace sortapplication
{
/// <summary>
/// 稳定的最小堆。（数组实现）
/// </summary>
/// <typeparam name="key">最小堆中保存的元素类型。</typeparam>
public class minpqstable<key> : iminpq<key>, ienumerable<key> where key : icomparable<key>
{
protected key[] pq; // 保存元素的数组。
protected int n; // 堆中的元素数量。
private long[] time; // 元素的插入次序。
private long timestamp = 1; // 元素插入次序计数器。
/// <summary>
/// 默认构造函数。
/// </summary>
public minpqstable() : this(1) { }
/// <summary>
/// 建立指定容量的最小堆。
/// </summary>
/// <param name="capacity">最小堆的容量。</param>
public minpqstable(int capacity)
{
this.time = new long[capacity + 1];
this.pq = new key[capacity + 1];
this.n = 0;
}
/// <summary>
/// 删除并返回最小元素。
/// </summary>
/// <returns></returns>
public key delmin()
{
if (isempty())
throw new argumentoutofrangeexception("priority queue underflow");
key min = this.pq[1];
exch(1, this.n--);
sink(1);
this.pq[this.n + 1] = default(key);
this.time[this.n + 1] = 0;
if ((this.n > 0) && (this.n == this.pq.length / 4))
resize(this.pq.length / 2);
debug.assert(isminheap());
return min;
}
/// <summary>
/// 向堆中插入一个元素。
/// </summary>
/// <param name="v">需要插入的元素。</param>
public void insert(key v)
{
if (this.n == this.pq.length - 1)
resize(2 * this.pq.length);
this.pq[++this.n] = v;
this.time[this.n] = ++this.timestamp;
swim(this.n);
//debug.assert(isminheap());
}
/// <summary>
/// 检查堆是否为空。
/// </summary>
/// <returns></returns>
public bool isempty() => this.n == 0;
/// <summary>
/// 获得堆中最小元素。
/// </summary>
/// <returns></returns>
public key min() => this.pq[1];
/// <summary>
/// 获得堆中元素的数量。
/// </summary>
/// <returns></returns>
public int size() => this.n;
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
public ienumerator<key> getenumerator()
{
maxpq<key> copy = new maxpq<key>(this.n);
for (int i = 1; i <= this.n; i++)
copy.insert(this.pq[i]);
while (!copy.isempty())
yield return copy.delmax(); // 下次迭代的时候从这里继续执行。
}
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
ienumerator ienumerable.getenumerator()
{
return getenumerator();
}
/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="k">需要上浮的元素。</param>
private void swim(int k)
{
while (k > 1 && greater(k / 2, k))
{
exch(k, k / 2);
k /= 2;
}
}
/// <summary>
/// 使元素下沉。
/// </summary>
/// <param name="k">需要下沉的元素。</param>
private void sink(int k)
{
while (k * 2 <= this.n)
{
int j = 2 * k;
if (j < this.n && greater(j, j + 1))
j++;
if (!greater(k, j))
break;
exch(k, j);
k = j;
}
}
/// <summary>
/// 重新调整堆的大小。
/// </summary>
/// <param name="capacity">调整后的堆大小。</param>
private void resize(int capacity)
{
key[] temp = new key[capacity];
long[] timetemp = new long[capacity];
for (int i = 1; i <= this.n; i++)
{
temp[i] = this.pq[i];
timetemp[i] = this.time[i];
}
this.pq = temp;
this.time = timetemp;
}
/// <summary>
/// 判断堆中某个元素是否大于另一元素。
/// </summary>
/// <param name="i">判断是否较大的元素。</param>
/// <param name="j">判断是否较小的元素。</param>
/// <returns></returns>
private bool greater(int i, int j)
{
int cmp = this.pq[i].compareto(this.pq[j]);
if (cmp == 0)
return this.time[i].compareto(this.time[j]) > 0;
return cmp > 0;
}
/// <summary>
/// 交换堆中的两个元素。
/// </summary>
/// <param name="i">要交换的第一个元素下标。</param>
-
您可能感兴趣的文章:
如对本文有疑问，
点击进行留言回复！！
SQLSERVER中RANK OVER(PARTITION BY)的用法
Kaspersky Endpoint Security 10 for Windows version 10.2.6.3733 is no longer supported
网友评论