数据结构与算法

平时开发中,一般很少用到手动来写算法的情况,但实际上我们一直在接触一些数据结构与算法,如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)

http://www.bigocheatsheet.com/

 

Bucket sort 排序

Bucket sort 排序 (图出自:极客时间)

计数排序 Counting sort

计数排序 Counting sort (图出自:极客时间)

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

算法时间复杂度和空间复杂度
时间复杂度:https://baike.baidu.com/item/时间复杂度/1894057
空间复杂度:https://baike.baidu.com/item/空间复杂度

复杂度大致可分为:

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

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次。