1.数据结构

• 数据结构：专门研究应用程序中数据之间逻辑关系、存储方式及其操作的学问

数据结构

• 集合：数据元素之间只有“同属于一个集合”的关系
• 线性关系：数据元素之间存在一个对一个的关系
• 树形结构：数据元素之间存在一个对多个的关系
• 图状结构或网状结构：数据元素之间存在多个对多个的关系

同一种的逻辑结构，在底层通常有两种物理存储结构。
算法的设计取决于逻辑结构；算法的实现依赖于存储结构。

• 栈（stack），是一种特殊的线性表，只能在固定在一端（线性表的尾端）进行插入、删除操作。

• 队列（queue），也是一种特殊的线性表，使用固定的一端（队尾rear）来插入数据，另一端（对头front）用于删除数据。

• 二叉树：在普通树的基础上，让一棵树中每个节点最多只能包含两个子节点，且严格区分左子节点和右子节点（位置不能换）。

• 哈夫曼树，一种带权路径最短的二叉树，在信息检索中很常用。

• 二叉排序树（Binary Sort Tree）,又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
  二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
  （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  （3）左、右子树也分别为二叉排序树；
  （4）没有键值相等的结点。
• 红黑树：一种更高效的检索二叉树，常用来实现关联数组。在实际编程中都有极为广泛的用途，例如JDK提供的集合类TreeMap就是一棵红黑树的实现。
  红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
  在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
  性质1. 节点是红色或黑色。
  性质2. 根节点是黑色。
  性质3 . 每个叶节点（NIL节点，空节点）是黑色的。
  性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2.排序

排序

直接选择排序：

1.在一组元素R[i]到R[n]中选择具有最小关键码的元素
2.若它不是这组元素中的第一个元素，则将它与这组元素中的第一个元素对调。
3.除去具有最小关键字的元素，在剩下的元素中重复1、2步，直到元素只有一个为止。

堆排序：

1. 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
2. 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交 换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
3. 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为 堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

堆 ：n个元素的序列{k1, k2, ..., kn},当且仅当满足
1）ki <= k(2i)且ki<=k(2i+1) (1 ≤ i ≤ n/2)
2）ki >= k(2i)且ki<=k(2i+1) (1 ≤ i ≤ n/2)
若将此排序码按顺序组成一颗排序二叉树，则
1）称为小顶堆（二叉树的所有节点值小于或等于左右孩子的值），
2）成为大顶堆（二叉树的所有节点值大于或等于左右孩子的值）。

冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

快速排序

1. 在数据集之中，选择一个元素作为”基准”（pivot）。
2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

插入排序

每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

直接插入排序

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中值包含一个元素，无序表中包含n-1个元素。排序过程中每次从无序表中去除第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

折半插入排序

• 折半插入排序是对直接插入排序的简单改进。
• 此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的插 入位置，这实际上是一种查找算法：折半查找。Java的Arrays类里的binarySearch()方法，就是折半查找的实现，用于从指定数组中查找指定元素，前提是该数组已经处于有序状态。
• 与直接插入排序的效果相同，只是更快了一些，因为折半插入排序可以更快地确定第i个元素的插入位置

希尔(shell)排序(缩小增量排序)

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

二路归并排序

将两个有序表合成为一个有序表。

桶式排序

桶式排序不再是一种基于比较的排序方法，它是一种非常巧妙的排序方式，但这种排序方式需要待排序列满足如下两个特征：

• 待排序列的所有值处于一个可枚举范围内
• 待排序列所在的这个可枚举范围不应该太大，否则排序开销太大

基数排序

基数排序已经不再是一种常规的排序方法，它更多地像是一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。
多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字：第1个子关键字、第2个子关键字、第3个子关键字。。。然后，根据子关键字对待排数据进行排序。
在进行多关键字排序时有两种解决方案：
最高位优先法MSD
最低位优先法LSD

总结

各种内部排序方法性能比较

1. 从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。
2. 从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图的“简单排序”中。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。
3. 从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序
4. 从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。

排序方法的选择

1. 若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。
2. 若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜。
3. 若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

</br></br></br></br>
END

---

以上内容根据<a href="http://www.atguigu.com/">尚硅谷</a>教学课件整理
PS:欢迎评论、指证，一起学习、探讨。