常用基本算法

分支主题

算法

排序

时间O（N^2）

冒泡排序

思路：0到n-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

 堆中有个数发生了变化，需要一直向下调整

时间：O(logN)

非递归空间O（1）；递归O(logN)

1、将数组变成大根堆

2、最后位置和堆顶位置交换

3、做heapify

4、重复2 3直到堆为0

时间O（N）

基数排序

非基于比较

空间O(M)

计数排序

空间O（M）