算法（第4版）

2.2.1

2.2.1

2.2.2

2.2.2

2.2.3

2.2.3

2.2.4 是 如果两子数组 EA CA 显然不可以 2.2.5 自底向上的很显然吗，最小的开始 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 8, 8, 8, 8, 7, 16, 16, 32, 39. 自顶向下 20|19 10|10 10|9 5|5 5|5 5|5 5|4 2/3 2/3 2/3 2/3 2/3 2/3 2/3 2/2 这样就很明显了 答案 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 3, 2, 5, 10, 20, 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 2, 4, 9, 19, 39. 2.2.6 对画图不是很熟悉，就打印出来了 自底向下和向上差不多，只在数组操作的时候N+2就好了。所以只贴了自顶向下的吧

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)));
    	}
    }
}

真的趋近于常数了 N:508， 访问数组次数:5190172,访问次数/Nlog(N):0.010778921009261398 N:509， 访问数组次数:5212406,访问次数/Nlog(N):0.010775941881986911 N:510， 访问数组次数:5234616,访问次数/Nlog(N):0.01077298026389605 N:511， 访问数组次数:5256892,访问次数/Nlog(N):0.01077002406446098 N:512， 访问数组次数:5279306,访问次数/Nlog(N):0.01076706379458834 2.2.7 因为每增加一个其中的最小的数组就+1 然后就显然就增加了至少一次比较次数！！！ 2.2.8 因为数组已经排序了，就不用调用merge（）函数，所以 T(N) = 2 T(N/2) + 1, with T(1) = 0. 2.2.9 在2.2.6题的代码中已经实现这样的方式了 2.2.10

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);
		}
		
	}
}

2.2.13

也是之前的笔记，暂时先放在这里保存下。

递归总有一个最简单的情况

递归调用总是去尝试解决一个规模更小的的子问题，这样递归才能收敛到最简单的情况

递归调用的父问题和尝试解决的子问题之间不应该有交集

【突然想到无副作用编程，其实编码的时候应该把有副作用和无副作用的程序给分隔开，这样子才好作测试】

2-3-4 树其实就是如何证明其能够保证平衡性，而其平衡性的保证其实是在于不可能有一条链路可以无限增长，因为当其大于某个阈值的时候，其会向上进行平衡

算法这本书呢有一个重要的思想是，先定义好这个数据结构的各种 api，有没有感觉很像设计模式的面向接口编程

深度优先搜索本质上是一种适用于处理有向图的算法。

不论是拓扑排序或者是最小生成树，其都要求无环

所谓编程也就是对现实中的抽象

排序的问题

有点慢慢明白了选择排序与冒泡排序的一些区别

选择排序虽然遍历是 N2，但是交换的话只是 N

冒泡排序的话能够更好地利用数组本身的有序性，如果一轮没有交换的话，可以提前终止排序

归并排序本身是对多个有序队列的最优排序

插入排序的应用场景是对一个本身已经有序的数组进行插入

插入排序的精髓是部分有序

如何比较两个算法：

实现并调试它们

分析他们的基本性质

对他们的相对性能作出猜想

用实验验证我们的猜想

希尔排序是插入排序的改进版本

【通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一】

算法导论中很多论证的部分，只是下意识我们都忽略了这一点

【人的大脑下意识都会去忽略这些最难的部分，应该说是不去想这些复杂的事情】

贪心是更多的是自顶向下，作出一个选择，然后求解剩下的那个子问题。

如何证明你所做到的局部最优解是全局最优解

动态规划更多的是自下向上

贪心算法的步骤

1、將最优化问题转化为这样的形式，对其作出一次选择后，只剩下一个子问题需要求解

2、证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的

3、证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心组合即可得到原问题的最优解，这样就得到了最优子结构

在每个贪心算法之下，几乎总有一个更加繁琐的动态规划算法

Leetcode的最大子序和的求解，有几点需要注意一下

1、测试用例要覆盖完整，能够覆盖各种特殊情况

2、要考虑到动态规划的结果数组的初始化，以免影响到其正常的比较

除了正常的动归之外应该还有分治法

仔细一想，虽然遍历，但时间复杂度还真是 O(n)的，不是自己一开始的认为是贪心方法可以求解

(再仔细一看，其实刚刚的思考是自己的心理盲区，自己心里总是想往正确答案方向去靠拢，所以才会出现这种明显的思维错误)

应该确实是贪心才能 O（n），其实这也是一种贪心的算法

求解三角形最小路径和

这道题目对于我最大的难点是构造合适的数据结构来进行处理，一开始没想到合适的数据结构，所以也就没有想出很好的自下向上的方法。

套娃信封问题有点像算法竞赛入门书中的矩阵嵌套的问题，但是不一样的是矩阵嵌套那里面可以旋转，但是这里的是不行的

书中推荐的是 DAG，有向无环图的方式，但那是因为可以旋转的话，判断起来会比较复杂么，如果是无法旋转的，理论上来说可以使用贪心方式来做，一个维度比较结束之后，第二个维度作为判断依据

但是如何排序是一个问题，主要是 key，value 的排序，如何用 value 排序完成之后，记住 key 的顺序呢，这个貌似也是一个很常见的问题，但是也一直没有总结。

没想到这个问题最终能够被抽象成为最长上升子序列的问题，而最长上升子序列我原本认为应该是有 O(n)的解法的，没想到其实是不行的，思维对于这些复杂的问题还是有一些没有完全理清楚的

越来越觉得算法导论这本书，很多地方真的过于抽象了

【怎么判断自己有没有成长呢】

要每一天都有所进步，不能只是停留在安逸区

LIS的问题也没有想象中的容易啊，DP 并不是就是完美的算法了，毕竟很多时候复杂度还是过高了。

[人对代码量的多少也会有一种天然的恐惧，代码多会下意识不想去看，这是不是也是思考快与慢里面的误区呢]

背景：

B-树的成本模型，我们使用页的访问次数（无论读写）作为外部查找算法的成本模型

才明白原来 B 树与 B+树的区别

B+树会将任何与关键字相联系的“卫星数据”和关键字一样存放在同一个节点中

最大程度减少树的高度

主存与磁盘访问的数据结构不一样最大原因就是访问主存的速度远远高于访问磁盘的速度

对于树，我们要关心其如何达到平衡的，各种各样的树，其是怎么保证平衡的

最大堆与优先队列的关系，最大堆可以实现优先队列

最大堆如何保持平衡性

插入元素，最后，然后开始向上调整，

关于图论

深度优先搜索的用途比想象中的还要大，其实有环与无环图都是可以搜索的

树其实也是一种特殊的图

图论的一些基本问题：

1、两个点之间是否是连通的

深度优先搜索能够解决，只要以 A 点开始遍历，看最终 B 点是否会被遍历为已标记

2、找出从 A 到 B 之间的路径

深度优先搜索遍历的时候，需要用一个额外的数组来记录找到 B 点的上一个节点是谁

算法这本书的组织真的很优秀，因为深度优先遍历在单源最短路径问题上的无能为力，所以引出了广度优先遍历

而普通的不带权的单源最短路径，确实可以用广度优先搜索来实现，只需正常遍历就可以求出单源最短路径，只要有一个额外的数组 edge 来保存就可以了。

3、求出一幅图所有的连通分量

【以前一直对这些概念其实挺模糊的，现在反复看也终于理解了这些概念了】

其实比自己想象的简单，就只需要对图进行深度优先遍历，从未遍历的点进行深度优先遍历。

为什么判断条件是值为-1？

还有下面的系统传递的参数是怎么回事？

4月7日完成了第一遍，但最后一章和字符串那章的后三节都还没看，有点看不动了。据说这本书正文的代码都要自己敲一遍，然而自己还没做到。

在纠结接下来是开始刷leetcode，还是写它配套的project，或是cs61b的作业，或是把正文代码再过一遍。