首页  思维导图  详情



 



常用基本算法

2018-10-13 16:17:35   35  举报





AI智能生成

程序员java面试常见算法

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）

分支主题

 Collect

Get Started

算法流程

 Collect

Get Started

图算法

 Collect

Get Started

外汇算法模型

 Collect

Get Started

算法流程





0 条评论

下一页