从代数开始
已知列数
已知一列数 a0,a1,a2,a3,…aN。 m,n是自然数，a(n)是无序常数
查找一个常数k,也就是说找到一个数a(n)=k。
二种可能性
(1.)数列中存在一个m,即a(m)=k；
(2.)数列中不存在k这个数，即没有a(m)=k；
查找方法
(1.)从数列头部开始，a0与k比较,a1与k比较,a2与k比较…aN与k比较。最多N次，可以知道，这个k值是否存在，在什么位置；
(2.)从数列尾部开始，aN与k比较,a(N-1)与k比较,a(N-2)与k比较,…,a(N-N)与k比较。也是最多N次，可以知道，这个k值是否存在，在什么位置；
(3.)其它查找，只要能遍历，每项只查找一次，也是最多N次，可以知道，这个k值是否存在，在什么位置；
那么世上为什么有那么多排序算法
上面的数列是已知的，就应该可以对它进行排序，把无序数列变成有序数列。
就像一个仓库有许多的物品盒子，我们入库时应该按照物品的种类、标签、大小分别放在不同的、指定的位置。这样，当我们提取物品时，就可以按照物品目录快速找到要提取的物品。
其实算法一点不神秘，只是把生活工作的事物写成公式和规范而已。
而且现实中每个仓库的摆放方法要远比我们已知的算法要多得多，复杂得多。
核心是【排序】
通常排序方法是有约定的，即类型相同。把现实模型进行了简化，或者说是抽象。
就好像把物品都统一到一样大小的盒子内，然后在盒子上写上标签。标名一个序号、重量或其它。
常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序。
冒泡排序，多次从头到尾两两比较大小，大小交换，直到全部有序。
选择排序，把最大或最小放到尾部或头部，把次最大或次最小放到次尾部或次头部，直到全部有序。
插入排序，从头对已经有的序数顺着下一个比较插入。
希尔排序，从头对已经有的序数从尾顺着比较插入。
归并排序，把数列分成等分直到有序，然后合成。
快速排序，找一个基准（计算机运算通常取第一个方便递归），左右分离，这几乎是人类生活工作排序的翻版。
堆排序，二叉搜索树的雏形。
非比较类排序：不通过比较来决定元素间的相对次序。
计数排序，对有相同值的数列排序。
桶排序，对数量较大时，把它们分到有限的区块（桶）再分别排序。
基数排序，对数据特征进行分桶排序。
这些排序方法其实在我们的生活工作中经常使用，并且是混合使用，比如生活生鲜的分检，仓库物质的摆放，产品的分类标签等等，只是很少会去注意到它们的专一特征和方法。
重要的【节点】（Node）
工作需求，日常排序工作是为了方便内容的进出和管理。就像计算机的数据管理，重要的工作是插入、删除、查找 如果没有节点分别，那么每次插入、删除可能需要对数据进行重排，如果数据很小，对计算没什么影响，但是通常数据量是非常巨大的，那么就会占用大量的计算资源，照成阻塞甚至崩溃。工作效率自然会让人难以接受。
人们想到了用节点来处理类似问题。这样二叉树的概念就诞生了，“输入的第一个数作为根结点，当继续输入数时，小于根结点的放在根结点左边，大于根结点的放在根结点右边，每个子节点也符合左小右大的规律。”
通俗来说就是一组有结点的数列。因为赋予了节点属性，许多的工作可以放到节点上进行，修改节点属性，而无需操作整个数组。这样工作效率会大大提高了。副产品是增大了数据的开销，因此数据量小时就不要一定使用节点。
数据结构的认知各人不同，如有偏颇在所难免，望批评原谅。
|