希尔排序：又称缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序，一般增量设置由大到小。
2.3 O(N) 算法思想：不是基于比较，而是来自于桶排序，桶排序的基本思想则是把数则是arr划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序：需要占用大量空间，它仅适用于数据比较集中的情况。比如[0~100]，[10000~19999]这样的数据，对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数，假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。
基数排序：实质为多关键字排序，思路是将待排数据里排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字等，然后，根据子关键字对待排序数据进行排序，如个位数，十位数，百位数等。
经典排序算法的空间复杂度
O(1)：插入排序、选择排序、冒泡排序、堆排序、希尔排序；
O(logN)~O(N)：快速排序；
O(N)：归并排序；
O(M): 计数排序、基数排序（和选择桶的数量有关）。
经典排序算法的稳定性
稳定性：假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。
稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序
不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
第三章字符串字符串特点：广泛性(1)字符类型数组；(2)其它类型题目可以看做字符串类型题目。Java处理字符串须注意String类在Java中不可更改，可尝试StringBuffer类，StringBuilder类和toCharArray方法处理。
字符串相关概念：回文；字串（连续）；子序列（不连续）；前缀树（Trie树）；后缀树和后缀数组；匹配；字典序
需掌握的操作：与数组有关的操作（增删改查）；字符的替换；字符串的旋转
常见类型：判断规则；数字运算；与数组操作有关的类型；字符计数；动态规划类型（最长公共字串等）；搜索类型；高级算法与数据结构解决的问题。
栈和队列基本性质：栈是先进后出，队列是先进先出；栈和队列在实现结构上可以有数组和链表两种形式（数组结构容易，链表涉及很多指针操作）
栈结构基本操作：pop；top或peek；push；size
双端队列：首尾都可以压入弹出元素；优先级队列：根据元素的优先级值，决定元素的弹出顺序，实为堆结构，并不是线性结构
深度优先遍历用栈来实现，宽度优先用队列实现，平时使用的递归函数实际上用到了提供的函数系统栈。
链表链表和数组区别：都是一种线性结构，数组是一段连续的存储空间，而链表空间不一定保证连续，为临时分配；
链表分类：按连接方向（单链表，双链表）；按照有无环分类（普通链表，循环链表）
代码实现的关键点：(1)链表调整函数的返回值类型，根据要求往往是节点类型；(2)处理链表过程中，先采用画图的方式理清逻辑；(3)对于边界条件处理。
插入删除注意事项：(1)特殊处理链表为空，或者链表长度为1的情况；(2)注意插入操作的调整过程；(3)注意删除操作调整过程。注意点：头尾节点及空节点需要特殊考虑。
单链表的翻转操作：(1)当链表为空或者长度为时，特殊处理；(2)对于一般情况如动画所示。
在有序序列中查找一个数，时间复杂度为O(logN);
并不一定非要在有序序列中才得到应用。
常见考察点对于边界条件的考察以及代码实现的能力
常见题目变化给定处理或查找的对象不同；
判断条件不同；
要求返回的内容不同。
重要提醒 mid = (left + right)/21
(left+right)可能会溢出，更安全的写法：
mid = left + (right - left)/21
位运算 常见操作符算术运算常见操作符：+ - * / %
位运算常见操作符：& | ^ ~ <<(左移右侧补0) >>(右移左侧补符号位) >>>(右移左侧补0)
案例