数据结构与算法

By admin

- One minute read - 88 words

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