数据结构与算法

平时开发中，一般很少用到手动来写算法的情况，但实际上我们一直在接触一些数据结构与算法，如 JAVA 中的ArrayList 就用到了数据结构与算法，从名字可以看到了用到了Array这种数组结构和链表结构。下面根据目前学习的情况做一个总结。

数据结构

我们常见的数组结构一般有：

• Array数组、
• Stack栈、
• Heap堆、
• Queue队列
• Hash 哈希类型
• LinkedList 链表，其中又分为单向链表、双向链表、还有最少用的环形链表
• Tree 这个Tree分的太多了，如B-Tree、 B+Tree(mysql使用)、Binary Search Tree二叉搜索树 、AVL高度平衡树、Red Black Tree红黑树 等

http://www.bigocheatsheet.com/

算法

一般开发中用到的基本上 排序 算法居多，而算法大体上又分为比较排序和非比较排序。我们常用的比较 排序算法 有(参考： http://www.cnblogs.com/eniac12/p/5329396.html )：

• 快速排序 （Quick Sort）
• 冒泡排序 （Bubble Sort）
• 插入排序 （Insertion Sort）
• 堆排序 （Heap Sort）
• 归并排序 （Merge Sort）

而非比较排序算法有（由于排序算法时间复杂度是线性的，有时候我们也称此算法线性排序，参考 http://www.cnblogs.com/eniac12/p/5332117.html ）：

• 计数排序（Counting sort）
• 基数排序 （Radix Sort）
• 桶排序 （Bucket Sort）

有些算法是属于稳定算法，有些非稳定算法，所谓的稳定是指相同的排序值原来的顺序经过排序后，前后顺序并不改变。就像我们平时数据库中根据两个字段进行排序的时候一样。

算法时间复杂度和空间复杂度

复杂度大致可分为

• O(1) 最好
• O(log n)
• O(n)
• O(n log n)
• O(n^2)
• O(2^n)
• O(n!) 最差

时间复杂度参考： https://baike.baidu.com/item/时间复杂度/1894057

O(log n)：当数据增大n倍时，耗时增大log n倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。 二分查找 就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

O(n log n)：同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。 归并排序 就是O(nlogn)的时间复杂度。

O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如 冒泡排序、插入排序、选择排序 ，就是典型的O(n^2)的算法，对n个数排序，需要扫描n x n次。