常用基本算法
2018-10-13 16:17:35 33 举报AI智能生成
程序员java面试常见算法
作者其他创作
大纲/内容
分支主题
分支主题
排序
时间O（N^2）
冒泡排序
思路：0到n-1位置上相邻比较，多次交换，大则交换
与原始序列顺序无关
空间O（1）
稳定
选择排序
思路：多次比较，一次交换
与原始序列顺序无关
空间O（1）
不稳定
插入排序
有序比较，多次移动
原始序列顺序有关
空间O（1）
稳定
时间O（N*logN）
快速排序
思路：分治，通过最后一个元素为中间值分组，并使其在中间位置，左边的比它小，右边的比它大，此时它在最终位置
与原始序列顺序无关
加速:通过荷兰国旗问题加速，一次确定与mid相等的所有元素的位置；通过random交换来打乱原有顺序
空间O（logN）（随机快排）最坏情况：O(N)
使用断点记录递归时每次划分的边界
不稳定
归并排序
思路：拆分小组，部分有序，合并相邻小组，使其有序
与原始序列顺序无关
空间O（N）
稳定
堆排序
堆结构：完全二叉树
数组结构实现，通过下标逻辑上变换得到逻辑上的完全二叉树
左孩子：2*i + 1
右孩子：2*i + 2
父节点：(i -1)/2
大根堆、小根堆
建堆heapInsert
把数组调整成大根堆：两层循环
时间：O（N）
调堆heapify
堆中有个数发生了变化，需要一直向下调整
选两个孩子中最大的孩子与当前结点交换，若当前结点最大，则结束，否则直到左子树超过heapSize,
时间：O(logN)
非递归空间O（1）；递归O(logN)
堆排序
1、将数组变成大根堆
2、最后位置和堆顶位置交换
3、做heapify
4、重复2 3直到堆为0
时间O（N）
基数排序
非基于比较
空间O(M)
稳定
计数排序
非基于比较
空间O（M）
分支主题
0 条评论
下一页
