八大排序 如果按照难易程度来区分(4个简单排序算法中除了基数排序剩下3个代码都是双重for循环) 4个简单直接插入排序简单选择排序、冒泡排序、基数排序 4个难希尔排序、堆排序、归并排序、快速排序 如果按照稳定性来区分 4个稳定直接插入排序、冒泡排序、归并排序、基数排序 4个不稳定简单选择排序、快速排序、希尔排序、堆排序交换变量的方式但奇数个数据会使中间值变为0有缺陷a a^b; b a^b; a a^b; a ab; b a-b; a a-b;直接插入排序: --可优化二分查找下标每一趟从待排序序列中取出一个值然后将其插入到己排序好的序列中默认第一个值是有序的最极端情况下如果默认已经有序直接插入排序的时问复杂度是0(n)数据越有序效率越好数据量不大时效率也挺高希尔排序--首先有一个缩小增量数组 gap默认规则: 1.数组中的值进行互素 2.增量从大到小的给值并且最后一个值一定得是1让数组整体变得有序 !!!选择排序每一趟从待排序序列中找出最小值所在位置然后将其和待排序序列第一个值所在位置进行交换冒泡排序 len个值需要len-1躺 --可优化加标签标记是否有交换每一趟从左向右两两比较如果左边值大于右边值则交换(相当于每一趟就可以将待排序序列中的最大值通过两两比较搬运的方式挪动到最后面)堆排序基于完全二叉树实现 将数组想象成一棵倒置的树映射关系时间复杂度O(n log n)空间复杂度O(1)建堆 → 交换堆顶与末尾 → 调整堆 → 循环直到有序第一次要彻彻底底对每一个非叶子节点排序大顶堆父节点 子节点子节点任意小顶堆父节点 子节点子节点任意父推子 -- 2i 1,2i 2;子推父 -- (i-1)/2归并排序核心合并函数先分在和递归实现使用双指针分别遍历两个数组每次取较小的元素放入结果数组一个数组用完后将另一个数组剩余部分直接追加比较头部的较小值依次取出直到合并完成。基数排序不比较数字大小按位分配。 不能处理负数从个位到高位依次将数字放入0-9的桶中再取出最后自动有序。执行过程找出最大值确定需要处理的位数从低位到高位每一轮都做两件事分配根据当前位0-9将数字放入对应的10个桶中//队列实现收集按0→9的顺序把桶里的数字依次取出处理完最高位后数组自动有序可以加一个偏移量负数最小值来处理负数和正数一样进行比较最后减掉偏移量。快速排序核心思想 分治法 基准点。//数据越有序效率越低 --要优化打乱越乱越好越有可能均分1.通过随机函数随机从待排数据里抽两个值进行交换2.三数取中法将最左端值最右端值最中间值三数中不大不小的那个值调整到最左边去;3.根据待排序序列元素个数N进行判断如果N过于小可以调用直接撤入/冒泡。选择一个基准元素将比它小的放左边比它大的放右边然后递归处理左右两部分。执行过程选基准通常选第一个或最后一个元素分区比基准小的放左边大的放右边基准归位递归对左右子数组重复上述过程直到有序BF算法枚举法暴力求解 判断是否匹配成功只看字串是否遍历走出字串范围return (i - j);//注意回退要回退到这一趟开始匹配的失败位置的下一个位置 i-j1kmp算法核心一句话变量i打死不回退不要让j无脑回退到0要寻找最长公共前后缀next数组(中间部分可以重叠寻找最长触底标记 -1 默认next数组开始为 -10