第一章

• 二分查找的速度比简单查找要快得多。
• O(log n)比O(n)快，需要搜索的元素越多，前者比后者就快得越多
• 算法运行的时间并不以秒为单位
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大O表示法表示。

第二章：选择排序

• 计算机内犹如一个大堆抽屉
• 需要存储多个元素时，可以使用数组或链表
• 数组的元素都在一起
• 链表的元素时分开的，其中每个元素都存储了下一个元素的地址
• 数组的读取速度很快
• 链表的插入和删除速度很快
• 在同一个数组中，所有元素的类型都必须相同

第三章：递归

• 递归指的是调用自己的函数
• 每个递归函数都有两个条件：基线条件和递归条件
• 栈有两种操作：压入和弹出
• 所有函数调用都进入调用栈
• 调用栈可能很长，这将占用大量的内存

数组 VS 链表

• 数组：内存空间连续，支持随机查找，所以查询高效O(1)时间复杂度，但是如果在中间插入或者删除时，由于需要移动数据所以性能较慢，O(n)，数组适合：读多写少的场景。
• 链表：内存空间不连续，每个节点会存储下个节点的地址，所以形成链表。链表特点：插入删除高效O(1)，查询数据O(n)；所以链表适合写多读少场景。

二分查找

/**
     * 非递归方式:
     * 1. 循环的判定条件是：low <= high
     * 2. 为了防止数值溢出，mid = low + (high - low)/2
     * 3. 当 A[mid]不等于target时，high = mid - 1或low = mid + 1
     * 时间复杂度: O(log2n) 空间O(1)
     */
    public static int binarySearch(int x, int[] ary) {
        int low = 0;
        int hight = ary.length - 1;

        while (low <= hight) {
            int mid = low + (hight - low) / 2; //注意：若使用(low+high)/2求中间位置容易溢出
            int t = ary[mid];
            if (t == x) {
                return t;
            } else if (t < x) {
                low = mid + 1;
            } else {
                hight = mid - 1;
            }
        }
        return -1;
    }  
       

选择排序

/** 
     * 它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
     * 存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
     * 然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
     * 选择排序是不稳定的排序方法
     */
    public static void selectSort(int[] ary) {
        for (int i = 0, selectTimes = ary.length; i < selectTimes; i++) {
            int min = i;
            for (int j = i + 1; j < selectTimes; j++) {
                if (ary[j] < ary[min]) {
                    min = j;
                }
            }
            //换元素
            int temp = ary[i];
            ary[i] = ary[min];
            ary[min] = temp;
        }
    }

第四章：快速排序

• 欧几里得算法
• D&C将问题逐步分解，使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
• 实现快速排序时，请随机地选择用作基准值的元素，快速排序的平均运行时间为O(nlogn)
• 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(nlogn)的速度比O(n)快的多

第五章：散列表

• 散列函数+数组可以创建散列表
• 冲突很糟糕，应该尽量避免冲突的散列函数
• 散列函数查找和插入和删除速度都很快
• 装载因子超过0.75就该调整散列表的长度

第六章：广度优先搜索

• 解决最短路径问题的算法被称为广度优先搜索BFS(breadth first search)
• 队列是先进先出的FIFO
• 栈是后进先出的LIFO
• 广度优先搜索关键点：顺序加入才是最短路径，所有需要使用队列，对于检查过的人，务必不再检查否则导致无限循环