代码实现参见github/algorithm中各个类别下wz包中的代码。

2.算法中常犯错误

2.1 插入排序——稳定排序

• 39）少了对数据索引范围的检查
• 40）同堆中siftUp siftDown一样，循环外的赋值出错了

            while (j >= 0 && e < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            // 这里之前赋值错写成了array[j] = e
            array[j + 1] = e;

2.2 希尔排序

• 41）while循环常犯的错误，三要素中忘了更新推进循环的变量

                while (j >= 0 && e < array[j]) {
                    array[j + increment] = array[j];
                    // 忘了更新j
                    j -= increment;
                }

2.3 冒泡排序——稳定排序

2.4 选择排序

2.5 归并排序——稳定排序

2.6 快速排序

• 42）递归算法，缺少终止条件

    private void sortCore(int left, int right) {
        // 注意，递归解法都有终止条件，千万不要缺少！
        if (right - left  <= 0) {
            return;
        }

• 43）for循环中i变量的初始状态不要想当然写成i = 0

    private int partition(int left, int right) {
        int mid = array[right];
        // less指向左边小于mid子数组最后索引的下一个
        // 这里注意less起始地址是left不是0
        int less = left;
        for (int i = left; i <= right - 1; i++) {
            // 算法导论的版本是<=，将小于等于的都放在左边
            if (array[i] <= mid) {
                swap(less++, i);
            }
        }

2.7 三向快速排序+三向字符串快速排序

• 44）长度、索引检测

        // 这里犯了严重错误，只有长度允许，才继续
        if (v.length() > d + 1) {
            sort2(low, high, d + 1);
        }

• 45）>=与>的区别

    private boolean less(String a, String b, int d) {
        for (int i = d; i < Math.min(a.length(), b.length()); i++) {
            // 犯了小错误，这里应该是charAt(i)而不是charAt(d)
            if (a.charAt(i) < b.charAt(i)) {
                return true;
            } else if (a.charAt(i) > b.charAt(i)) {
                // 这个地方刚开始写错了，写成了>=，应该是>，等于则必须向后
                return false;
            }
        }

• 总结：对于while循环，核心就是循环不变量，清晰定义循环不变量中各个变量表示的含义，以及循环不变量的状态是什么

2.8 堆排序

2.9 计数排序

2.10 字符串的低位优先排序

2.11 高位优先排序

• 46）索引检查

        // 少了索引检测
        checkValid(low, high);
        if (high - low + 1 <= MIN_LENGTH) {
            insertionSort(low, high, d);
            // 少了return
            return;
        }

2.12 外排序——多路归并排序

2.13 二分查找

2.14 查找第k个数