Data-Structure = (D,R)

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

数据元素之间存在的关联关系被称为数据的逻辑结构。
归纳起来，应用程序中的数据大致有如下四种基本的逻辑结构：
集合：数据元素之间只有“同属于一个集合”的关系
线性关系：数据元素之间存在一个对一个的关系
树形结构：数据元素之间存在一个对多个的关系
图状结构或网状结构：数据元素之间存在多个对多个的关系

同一种的逻辑结构，在底层通常有两种物理存储结构：
顺序存储结构
一维数组
非顺序存储结构
链式存储结构（链表）、散列结构

算法的设计取决于逻辑结构；算法的实现依赖于存储结构

对于普通线性表而言，它的作用是一个容器，用于盛装具有相似结构的数据。
分为顺序存储结构和链式存储结构
可以进行插入、删除和排序的操作
如果是线性表，只允许在线性表的某端添加、删除元素，这时就演变为：栈和队列

栈（stack）

是一种特殊的线性表，只能在固定在一端（线性表的尾端）进行插入、删除操作。
允许进行插入、删除操作的一端为栈顶top，另一端为栈底bottom。

进栈：将一个元素插入栈的过程。栈的长度+1。“压入栈”
出栈：删除一个元素的过程。栈的长度-1。“弹出栈”

先进后出，或说后进先出。
常用操作：初始化。
分为顺序栈结构和链式栈结构

队列（queue）

也是一种特殊的线性表，使用固定的一端（队尾rear）来插入数据，另一端（对头front）用于删除数据。先进先出。
分为顺序队列结构和链式队列结构
从JDK1.5开始，java集合框架提供了Queue接口。实现该接口的类可以当成队列使用。

树

也是一种数据结构，非线性的，这种结构内的元素存在一对多的关系。
树，尤其是二叉树应用很广泛。哈夫曼树和哈夫曼编码就是二叉树的重要用途。

二叉树：在普通树的基础上，让一棵树中每个节点最多只能包含两个子节点，且严格区分左子节点和右子节点（位置不能换）
遍历二叉树，考虑深度优先遍历(先序遍历、中序遍历和后序遍历)和广度优先遍历。

哈夫曼树，一种带权路径最短的二叉树，在信息检索中很常用。
哈夫曼编码，假设需要对一个字符串如“abcdabcaba”进行编码，将它转换为唯一的二进制码，同时要求转换出来的二进制码的长度最小。我们采用哈夫曼树来解决报文编码问题。

排序二叉树：一种特殊的二叉树，可以非常方便地对树中的所有节点进行排序和检索。
满足一些条件的二叉树，才被称为排序二叉树。比如：若它的左子树不为空，左子树上的所有节点值均小于根节点值；若右子树不为空，右子树上的所有节点值均大于根节点值。

红黑树：一种更高效的检索二叉树，常用来实现关联数组。在实际编程中都有极为广泛的用途，例如JDK提供的集合类TreeMap就是一棵红黑树的实现。
红黑树在只读操作上，跟普通排序二叉树上的只读操作相同，只是检索性能好。对于删除和插入操作可能导致树不再符合红黑树的特征。（需要进行颜色的调换）

红黑树的特性：首先满足排序二叉树的特性；每个节点要么红色，要么黑色；根节点是黑色的；所有叶子节点都是null且为黑色；红色节点的两个子节点是黑色的；从任一节点到其子树的每个叶子节点的路径都包含相同数量的黑色节点）

排序：

排序：假设含有n个记录的序列为{R1， R2， ...,Rn},其相应的关键字序列为{K1， K2， ...,Kn}。将这些记录重新排序为{Ri1,Ri2,...,Rin},使得相应的关键字值满足条Ki1<=Ki2<=...<=Kin,这样的一种操作称为排序。通常来说，排序的目的是快速查找。

衡量排序算法的优劣：

1.时间复杂度：分析关键字的比较次数和记录的移动次数。
2.空间复杂度：分析排序算法中需要多少辅助内存。
3.稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

排序算法分类：

内部排序和外部排序。

内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。

外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

十大内部排序算法：

选择排序
直接选择排序、 堆排序
交换排序
冒泡排序、 快速排序
插入排序
直接插入排序、 折半插入排序、 Shell排序
归并排序
桶式排序
基数排序

算法的五大特征：

直接选择排序：

基本原理：
将待排序的元素分为已排序（初始为空）和未排序两组，依次将未排序的元素中值最小的元素放入已排序的组中。

冒泡排序：

排序思想：

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

快速排序：

排序思想：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 递归的最底部情形，是数列的大小是零或一，也就是元素都已经被排序好了。一直递归下去这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

折半插入排序：

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

排序算法比较：

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

排序算法的选择：

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

数据结构和排序

原文：https://www.cnblogs.com/088-p/p/14587121.html