希尔排序、归并排序、快速排序，KMP
再说这三种排序前，先对比下这几种排序的复杂度。
1.希尔排序
希尔排序的思想是以分组的方式，分而治之。
核心思想:一边分组一边排
例如把10个数据，分为5组，5组里面，小的放在左边，大的放在右边。第二次，再把它分为4组，依然是小的放左边，大的放在右边。分组的次数越多，交换的次数越小。也可以把希尔排序看作一次分组的插入排序。
希尔排序空间存储比较小o(1)，适合空间复杂度比较小的场景。如果空间复杂度比较大，一般都是外排序。
稳定和不稳定的意思是什么？
比如集合中，有2个数一样，但是两个数经过排序后，依然顺序不变，这就是稳定性，否则就是不稳定。最好情况和最坏情况不一样。
2.归并排序
核心思想:先分组，再合并排序。
归并排序（采用了递归的思想）:归并排序，特殊的地方就是，需要记住前后游标的位置。其它只要记住数据集合和长度就可以。
把一个集合逐级分组，具体如下。
1. 先把集合中的元素，分为2部分。
2. 然后再上面2分的基础，再分为4部分。
3.直到每个集合里面只有2个元素时，进行排序。
4. 排序完后，然后再合并到一起。
归并排序测试:
3.快速排序
核心思想:一轮游确定哨兵，哨兵分两边，两边再递归
1. data[i],就只是一个移动的哨兵。如果data[j]对应的值比data[i]大，则j往后移动，反之i往前移动，并实现交换。
2.当i和j相等的时候，哨兵的位置就确定下来了。
3. 经过步骤2的比较，再分成最后两个集合递归执行。
快速排序测试:
4.KMP算法
如果给定字符串ABCABD。
寻找子串。
详细剖析:
左侧是前缀，右侧是后缀，观察前缀和后缀公共元素的个数。
pattern是给定的字符串。
kmp有个回溯的功能，就是用一个数组去存储公共资源的相同部分的数量，把这个数量就依次存储到数组里面。这个数组，是用作回溯用的。这个数组的目的是如果pattern中有重复字符，那么在查找的时候，前面已经比较过的相同字符就无需再对比，进而寻找到最大子串。
欢迎关注头条号