Robert Sedgewick 斯坦福大学博士,导师为Donald E. Knuth,从1985年开始一直担任普林斯顿大学计算机科学系教授,曾任该系主任,也是Adobe Systems公司董事会成员,曾在Xerox PARC、国防分析研究所(Institute for Defense Analyses)和法国国家信息与自动化研究所(INRIA)从事研究工作。他的研究方向包括解析组合学、数据结构和算法的分析与设计、程序可视化等。
Kevin Wayne 康奈尔大学博士,普林斯顿大学计算机科学系高级讲师,研究方向包括算法的设计、分析和实现,特别是图和离散优化。
这书就是一场大型的mindfuck。它只是向一个向往严肃精神生活的人指明,你再怎么折腾也只能是智力界的amateur。它是一次长征。当你踉踉跄跄淌过sorting和searching两章,还在为红黑树心有余悸的时候,却不期已陷入graphs的沼泽中。在无数次为Prim或Dijkstra的trace of stack揉搓...
(展开)
package edu.algorithms.sort;
import StdLib.StdIn;
import StdLib.StdOut;
public class Merge {
// This class should not be instantiated.
private Merge() { }
//记录访问数组次数
private static int N = 0;
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
N = N + 2; //复制
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
N = N + 2;
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i]))
{
N = N + 2;
a[k] = aux[j++];
}
else a[k] = aux[i++];
}
// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}
/***********************************************************************
* Helper sorting functions
***********************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***********************************************************************
* Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
/***********************************************************************
* Index mergesort
***********************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) index[k] = aux[j++];
else if (j > hi) index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else index[k] = aux[i++];
}
}
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation <tt>p[]</tt> such that <tt>a[p[0]]</tt>, <tt>a[p[1]]</tt>,
* ..., <tt>a[p[N-1]]</tt> are in ascending order
*/
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i;
int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; mergesorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
// String[] a = StdIn.readAllStrings();
// Merge.sort(a);
// show(a);
for(int i = 1 ; i<=512 ; i++)
{
Double[] a = new Double[i];
for(int j = 0 ; j < a.length ;j++)
{
a[j] = Math.random();
}
Merge m = new Merge();
m.sort(a);
System.out.println("N:" + i + ", 访问数组次数:" + m.N + ",访问次数/Nlog(N):" + m.N/(6*N * Math.log(N)));
}
}
}
private static void merge(Comparable[] a, int lo, int mid, int hi) {
for (int i = lo; i <= mid; i++)
aux[i] = a[i];
for (int j = mid+1; j <= hi; j++)
aux[j] = a[hi-j+mid+1]; //将另一个数组按降序排到j=mid + 1开始
int i = lo, j = hi; //现在aux[hi] 是之间的a[mid +1],之后的就好理解了
for (int k = lo; k <= hi; k++)
if (less(aux[j], aux[i])) a[k] = aux[j--];
else a[k] = aux[i++];
}
2.2.11
package edu.algorithms.sort;
import StdLib.StdIn;
import StdLib.StdOut;
public class MergeX {
private static final int CUTOFF = 7; // cutoff to insertion sort
// This class should not be instantiated.
private MergeX() { }
private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
// precondition: src[lo .. mid] and src[mid+1 .. hi] are sorted subarrays
assert isSorted(src, lo, mid);//检测数组是否已经有序
assert isSorted(src, mid+1, hi);
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) dst[k] = src[j++];
else if (j > hi) dst[k] = src[i++];
else if (less(src[j], src[i])) dst[k] = src[j++]; // to ensure stability
else dst[k] = src[i++];
}
// postcondition: dst[lo .. hi] is sorted subarray
assert isSorted(dst, lo, hi);
}
private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
// if (hi <= lo) return;
if (hi <= lo + CUTOFF) { //利用插入排序来加快小叔子的排序速度
insertionSort(dst, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(dst, src, lo, mid);
sort(dst, src, mid+1, hi);
// if (!less(src[mid+1], src[mid])) {
// for (int i = lo; i <= hi; i++) dst[i] = src[i];
// return;
// }
// using System.arraycopy() is a bit faster than the above loop
if (!less(src[mid+1], src[mid])) {
System.arraycopy(src, lo, dst, lo, hi - lo + 1);//利用java库函数来加快数组的复制
return;
}
merge(src, dst, lo, mid, hi);
}
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = a.clone();
sort(aux, a, 0, a.length-1);
assert isSorted(a);
}
// sort from a[lo] to a[hi] using insertion sort
private static void insertionSort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}
// exchange a[i] and a[j]
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
// is a[i] < a[j]?
private static boolean less(Comparable a, Comparable b) {
return (a.compareTo(b) < 0);
}
/***********************************************************************
* Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; mergesorts them
* (using an optimized version of mergesort);
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
MergeX.sort(a);
show(a);
}
}
2.2.12
修改后的选择排序
public class Selection {
public static void sort(Comparable[][] a)
{
int N = a.length;
for(int i = 0; i < N; i++)
{
int min = i;
for(int j = i ; j < N ; j++)
{
if(less(a[0][j],a[0][min]))
{
min = j;
}
exch(a,i,min);
}
}
}
private static boolean less(Comparable v,Comparable w)
{
return v.compareTo(w) < 0;
}
private static void exch(Comparable[][] a ,int i ,int j)
{
Comparable t = a[0][i];
a[0][i] = a[0][j];
a[0][j] = t ;
}
private static void show(Comparable[] a )
{
for(int i = 0; i < a.length ; i++)
{
System.out.print(a[i] + " ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a)
{
for(int i = 1 ; i < a.length ; i++)
{
if(less(a[i],a[i-1]))
{
return false;
}
}
return true;
}
}
主代码
package edu.algorithms.sort;
public class Twelve {
public static void main(String[] args) {
int N = 16;
Double[] a = new Double[N];
int M = 4;
for(int i = 0 ; i < N ;i++)
{
a[i] = Math.random();
}
Double aux1[] = {a[0],a[1],a[2],a[3]};
Double aux2[] = {a[4],a[5],a[6],a[7]};
Double aux3[] = {a[8],a[9],a[10],a[11]};
Double aux4[] = {a[12],a[13],a[14],a[15]};
Double[][] aux = {aux1,aux2,aux3,aux4};
Selection.sort(aux);
for(int i =0 ; i < aux.length ; i++)
{
for(int j = 0 ; j < M ; j++)
{
}
}
System.arraycopy(aux1, 0, a, 0, M-1);
System.arraycopy(aux2, 0, a, M, 2*M-1);
System.arraycopy(aux3, 0, a, 2*M, 3*M-1);
System.arraycopy(aux4, 0, a, 3*M, 4*M-1);
for(int i = 0 ; i < M;i++)
{
Merge.merge(a[i], a[i], i, i + M, i + 2*M);
}
}
}
To understand mergesort, it is worthwhile to consider carefully the dynamics of the method calls, shown in the trace at right. To sort a[0..15], the sort() method calls itself to sort a[0..7] then calls itself to sort a[0..3] and a[0..1] before finally doing the first merge of a[0] with a[1] after calling itself to sort a[0] and then a[1] (for brevity, we omit the calls for the base-case 1-...
2019-10-13 22:31
To understand mergesort, it is worthwhile to consider carefully the dynamics of the method calls, shown in the trace at right. To sort a[0..15], the sort() method calls itself to sort a[0..7] then calls itself to sort a[0..3] and a[0..1] before finally doing the first merge of a[0] with a[1] after calling itself to sort a[0] and then a[1] (for brevity, we omit the calls for the base-case 1-entry sorts in the trace). Then the next merge is a[2] with a[3] and then a[0..1] with a[2..3] and so forth. From this trace, we see that the sort code simply provides an organized way to sequence the calls to the merge() method. This insight will be useful later in this section.引自 merge sort
5 有用 Hari 2013-04-11
这本书也非常牛,用java实现,我觉得这本书是最适合用来算法入门的,说它适合入门不是说它太浅,而是讲的深入浅出,非常容易理解,里面那些小彩图呀,啧啧,美极了!建议中英对照着读。
1 有用 eval 2017-04-18
讲得非常清楚明白
1 有用 阅微草堂 2016-01-07
模型理论算法(本书缺前两项),举例假设联系学会分别。
3 有用 灵茶山艾府 2014-06-04
这种书读一本少一本,真的。
3 有用 Priver 2018-04-12
这本应该算是最简单的算法书了,但是真心觉得算法难啊,全是干货。。
0 有用 小猪快跑 2021-01-16
终于肝完:从11月初到1月中,10~20页/天,补足了最薄弱的算法基础,未来可期,加油!!!
0 有用 丿尘灬埃 2021-01-15
我觉得一般吧,没有算法导论强。
0 有用 ヤ尐壞疍_)á 2021-01-09
第一本算法书时,我觉得很好,看了其他算法书后,我又嫌弃其太过"学院化",当时看的时候好多概念看不懂,也不知道是不是翻译的锅,这本书精华是代码,有部分图可以,部分图不看解释,不知道画的是啥,API设计巧妙,实现巧妙,但是其中部分变量却没解释清楚对应的逻辑事物,而看文中解释有过于严谨,我希望的更多是作者指着一个图,告诉我这就是图,指着一个树,告诉我这就是树,而不是告诉一些概念的堆切。总得来说,挺值的,... 第一本算法书时,我觉得很好,看了其他算法书后,我又嫌弃其太过"学院化",当时看的时候好多概念看不懂,也不知道是不是翻译的锅,这本书精华是代码,有部分图可以,部分图不看解释,不知道画的是啥,API设计巧妙,实现巧妙,但是其中部分变量却没解释清楚对应的逻辑事物,而看文中解释有过于严谨,我希望的更多是作者指着一个图,告诉我这就是图,指着一个树,告诉我这就是树,而不是告诉一些概念的堆切。总得来说,挺值的,但是还是过誉了,特别对于初学者不利于入门。 (展开)
0 有用 Charles 2021-01-09
读了开头,并卖了(再见吧计算机算法😄
0 有用 约克哈特 2021-01-08
现在回过头看,用java这种带泛型的面向对象语言讲数据结构确实是个非常好的做法。另外这本书在内容组织上结构非常清晰,正文只细讲最重要的数据结构和算法, 把一些较次要的算法和优化放到习题里。美中不足的是内容还是略少。