算法

排序算法

时间复杂度O(n² )

 冒泡排序

算法过程：1、大循环，从第一个元素i遍历到最后一个元素arr.length-12、小循环，从第一个元素j遍历到最后一个元素arr.length-i-13、大循环标记是否发生交换isSorted，isSorted为true则结束（优化点：确定是否提前结束循环）4、小循环设置lastExchangeIndex，大循环确定有序边界sortBorder=lastExchangeIndex，j遍历到sortBorder（优化点：确定有序边界）

鸡尾酒排序：1、大循环控制从i到数组最后一个元素的遍历；2、小循环从左遍历到右，然后从右遍历到左

选择排序

插入排序

希尔排序

时间复杂度O(nlogn)

快速排序

算法过程：（核心点分治法）1、随机选择一个基准点pivot2、设定left、right指针，如果left != right，则有以下判断：①如果left <= pivot，left++;②如果right > pivot，right--；③都不符合，则把left和right的元素交换；如果left == right，则把left和pivot元素交换，返回left下标；3、把得到的left下标设为基准点pivot，①startIndex，pivot-1的范围再继续做快速排序；②pivot+1、endIndex的范围再继续做快速排序；4、如果startIndex >= endIndex，则结束排序。

归并排序

堆排序

时间复杂度O(n)

计数排序

算法过程：1、创建最大数-最小数的范围数组2、遍历数组，把对应下标的数字+13、最后把每个数组元素+前一个数组元素的和作为当前元素的值4、排序数组时，当前元素的值-1

缺点：1、数据分布不平衡时，会创建很多没有用的数组空间2、不是整数无法采用下标

桶排序

算法过程：1、求出最大数、最小数2、根据元素数量创建对应的桶3、遍历原始数组，分配到各个桶，依据算法（每个元素-最小数）* 桶的数量-1 / (最大数-最小数）4、对每个桶的元素进行排序5、遍历桶得到结果

缺点：1、数据分布不平衡时，一样会存在浪费空间

基数排序

面试题

如何判定一个链表是有环链表？

扩展：1、如何求出环的长度？2、如何求出入环节点？

算法：1、设定两个指针p1、p2，p1指向元素next，p2指向元素next.next2、当p2指向元素不为null，p2.next指向元素不为null，则不停地检测p1，p2所指向元素是否相等，相等则有环

实现一个栈，该栈带有出栈、入栈、取最小元素3个方法，要保证这3个方法的时间复杂度都是O(1)？

算法：1、栈A存储原始数组，栈B存储最小数2、当出栈时，如果栈A和B的栈顶相同，则栈B出栈，当前栈顶仍然有最小元素

求出两个整数的最大公约数？

算法：1、碾转相除法2、更相减损术3、更相减损术+移位算术

如何判断一个数是否为2的整数次幂？

算法：1、num&num-1进行与运算，结果为0则符合

无序数组排序后的最大相邻差？

算法：1、借助桶排序的算法，每个桶统计最大数和最小数2、比较相邻两个不为空的桶的A、B，B的最小值减去A的最大值，就是最大相邻差

如何用栈实现队列？

算法：1、栈A实现入队2、栈A弹出栈的元素，作为栈B的入栈数据，栈B出栈实现出队

找出一个正整数所有数字全排列的下一个数？（核心：字典序算法）

算法：1、假设原始数组A，找出A中倒序的元素下标index2、从A最后一个元素开始比较，比较index-1的元素X，如果X小于最后一个元素，则交换元素3、从A最后一个元素开始比较，比较index的元素Y，如果Y大于最后一个元素，则交换元素输出结果，即为全排列的下一个数

给出一个整数，删去k个数字后的最小值？（核心：贪心算法）

普通算法：1、把整数用数组A存储2、循环K次，每次把A从左到右比较大小，当左边元素大于右边元素时，则删掉左边的数字3、打印数组得到结果

进阶算法：1、创建一个整数字符串A长度的栈B，得到A.length-K后的新长度L2、遍历A的元素X在栈B入栈3、如果栈B栈顶的元素大于当前A遍历的元素X，则X覆盖栈顶的元素，相当于让B出栈4、找到栈中第一个非零数字的位置Offset，截取栈B从Offset到L的范围数字，得到结果

如何实现大整数相加？

算法

物理存储结构

数组

查找：时间复杂度O(1)插入：时间复杂度O(n)

扩容：把原来的数组长度 x 2

链表

查找：时间复杂度O(n)插入：时间复杂度O(1)

逻辑存储结构

线性结构

栈

后进先出

队列

先进先出

哈希表

哈希函数：对Key进行HashCode，得到一个数字下标

扩容：把原来的数组长度 x 2，重新哈希取模

非线性结构

二叉树

二叉排序树:时间复杂度O(logn)最坏情况O(n)

满二叉树

完全二叉树

树的自平衡

红黑树

AVL树

树堆

遍历

深度优先遍历

前序遍历

每一个节点，递归实现根->左节点->右节点

中序遍历

每一个节点，递归实现左节点->根->右节点

后序遍历

每一个节点，递归实现左节点->右节点->根

广度优先遍历

层序遍历

借助队列实现，把树的根节点入队列，如果队列不为空，继续以下过程：①输出当前队列的队首节点，查找该节点的左右节点，如果存在则入队列②重复第一步

二叉堆

最大堆、最小堆：插入元素进行比较上浮删除元素进行比较下沉

优先队列