1. 数据结构部分

数据结构中常用的操作的效率表

通用数据结构

查找 

插入 

 删除

遍历 

数组

O(N)

O(1)

O(N)

—

有序数组

O(logN)

O(N)

O(N)

O(N)

链表

O(N)

O(1)

O(N)

—

有序链表

O(N)

O(N)

O(N)

O(N)

二叉树

O(logN)

O(logN)

O(logN)

O(N)

二叉树（最坏）

O(N)

O(N)

O(N)

O(N)

红黑树

O(logN)

O(logN)

O(logN)

O(N)

2-3-4树

O(logN)

O(logN)

O(logN)

O(N)

哈希表

O(1)

O(1)

O(1)

—

专用数据结构

 

 

 

 

栈

—

O(1)

O(1)

—

队列

—

O(1)

O(1)

—

优先级队列

—

O(N)

O(1)

—

优先级队列（堆）

—

O(logN)

O(logN)

 

2. 排序算法

常见的排序算法比较表

排序

平均情况

最好情况

最坏情况

稳定与否

空间复杂度

冒泡排序

O(N²)

O(N)

O(N²)

稳定

1

选择排序

O(N²)

O(N²)

O(N²)

不稳定

1

插入排序

O(N²)

O(N)

O(N²)

稳定

1

希尔排序

O(NlogN)

（依赖于增量序列）

不稳定

1

快速排序

O(NlogN)

O(NlogN)

O(N²)

不稳定

O(logN)

归并排序

O(NlogN)

O(NlogN)

O(NlogN)

稳定

O(N)

二叉树排序

O(NlogN)

O(NlogN)

O(N²)

稳定

O(N)

堆排序

O(NlogN)

O(NlogN)

O(NlogN)

不稳定

1

拓扑排序

O(N+E)

—

—

—

O(N)

首先先给出我们常用的算法的时间复杂度，后面会具体讲解每一个算法，以及在不同的场合下哪种时间复杂度很高效