一个资深架构师是这样理解数据结构的

计算机里面最基本的数据结构是数组（比之更基本的是存储单元，但单独的存储单元不能构成结构），我们的软件逻辑就是针对数据结构的一系列操作，所有的更复杂的数据结构都是基于数组演化而来的。数组可以被规约为一组有连续下标（编号）的盒子，编号大于等于零。那么针对数组的基本操作就有检索（Search）、修改（modify）、添加（Append）、插入（Insert）、删除（delete）等。

检索和时间复杂度

数组的检索操作又是所有其他操作的基础，因为要让程序逻辑进行正确的动作，必须首先找到正确的位置。那么针对数组的检索方式又有两种：按照下标检索和按照内容检索。他们的时间复杂度分别是：

按照下标检索=O(1) 
按照内容检索=O(n)，n为数组长度。

当数组为一个有序数组的时候，按照内容的检索速度就可以得到提升。我们都知道折半查找的方法，首先与数组中间位置的内容比较，确定要检索的在左边还是右边，然后将这个过程递归下去直到找到。这样一来，比较的次数最大就不是n次，而是log2n次了。

由于是折半查找，所以log的底就是2，可能有人会问为什么不能以更大的数为底，这样不是查找的次数更少了么？其实，这里有个恶化的问题，折半查找时目标要么在左侧要么在右侧，左右两边相等，所以无论在左侧还是右侧，算法都所消耗的比较次数都相等；但是如果以更高数为底（比如10），运气不好的话目标值总是落到十分之九那一侧，算法就会恶化，所以选择最平衡的2分法是稳妥高效的。

于是有序数组的内容检索时间复杂度=O(logn)，对于按照内容检索来说，折半查找是目前已知的稳定的最快的检索算法了。

下面我们谈谈如何让数组有序。

数组的排序

对于一个无序的数组，最直观的排序方法就是选择排序了，我们会先创建一个空的数组，然后从原来的数组中找到最小的那个数，放在空数组的第一位；再找到次小的数放在第二位，依次类推就得到了一个有序数组。

实际上，选择排序的方法可以规约为在无序数组中做n次检索的过程，由于无序数组按内容检索的时间复杂度为O(n)，所以选择排序的时间复杂度就可以近似的等于n*O(n)=O(n^2)。显然，选择排序的损耗随数组大小呈指数上升，这个算法是不能接受的。

那么很自然的，我们会想到将无序检索变为有序检索。同样的，我们创建一个空的数组，并且从无序数组中取得一个值放入空数组中，当我们取第二个值放入空数组中时根据与第一个值比较的大小，选择将这个值插入到第一个值得前面或后面，这样就形成了一个有序的数组；依次类推，每次取得一个值都通过折半查找的方式在有序数组中找到合适的位置插入，最终完成排序。假设我们忽略数组插入的损耗，那么由于有序数组的时间复杂度为O(logn)，最终这种算法的时间复杂度就近似的等于n* O(logn)= O(n*logn)。

由于O(logn)是目前已知的稳定的最快的按内容检索的算法，所以无论任何一种排序的变种，只要是按照内容进行比较的，都不可能比这个更能同时满足快和稳定了。唯一能够缩减的，就是我们上面忽略的插入损耗，这也是所有按内容排序变种所优化的地方。

快速排序（Quicksort）

快速排序很多人说是冒泡的变种，其实我觉得这是典型的折半法的变种。快排的基本思想是，将数组分成左右两半，让左边的数都比右边的数小；然后再次对左右两侧折半，直到完成。不过，由于快排的折半策略是基于某一个随机选定的数值的，所以不一定能够恰巧选择一个中间值，因此快排是有可能恶化的，但也正是由于这一点使得log的底可以大于2，所以快排有可能比二分更快。在此，我不去细说快排的具体算法，因为随便百度就可以得到，不需要我来解释。

归并排序（Mergesort）

归并排序的基本思想是将两个有序数组合并成一个有序数组，从无序数组的初始态开始，每一个元素都可以看作一个有序数组，所以第一次合并近似形成n/2个拥有两个元素的有序数组，第二次合并近似形成n/4个拥有4个元素的有序数组，依次类推最终得到排好序的数组。这个过程实际上是个颠倒的折半过程，我们习惯于说这是通过分治法的原则来解决问题，实际上折半查找也算分治法的一种实现。

归并排序的具体算法网络上也随手可得，我这里就不多介绍了。比较麻烦的是如何计算归并排序的时间复杂度，推导过程的数学公式比较复杂枯燥，感兴趣的同学可以向我索取，这里就不展开了。直观的看，一个颠倒的折半查找是O(logn)，每次的合并需要比较最多数组的大小n次，所以归并排序的时间复杂度依然是O(n*logn），我们前面说过这是不可能突破的物理极限了。由于归并算法是标准的折半，所以其稳定度是有保障的。这种算法的好处是通过增加辅助的空间，来降低数组的插入损耗。

一些数组的变种

在继续探讨更多排序算法之前，我们不得不停下来引入一些新的数据结构，因为数组这个结构实在是太基础了，不能够承载太多的算法。

堆和栈

堆和栈是数组最简单的变种，我相信堆先进先出和栈先进后出的概念已经融入程序员的血液之中了，我这里就不说了。

链表

链表要解决的是数组的插入损耗问题，链表是数组的一种非常极端的变种，当我们完全不需要在数组中进行检索的时候，插入损耗成为最大的消耗。于是，我们将数组拆成单一元素的数组，然后用头尾两个指针进行串接，就形成了链表。

链表的最大好处就在于，插入或删除一个元素的时候，比数组快n倍是O(1)。其坏处是，无法用折半的方式进行检索。

哈希表

哈希表是数组的一个非常重要的变种，我们知道数组最快的检索方式是按照下标检索，其时间复杂度是O(1)，那么哈希表就是这么一个天才的设计，他能够将按照内容检索的方式转变成按照下标检索。

我们知道，当数组的内容是纯粹的数字时，理论上我们可以将内容作为下标，这样的话我们就可以用内容作为下标直接检索到相应的内容了，当然这可能没有任何实际意义。哈希表将存储的内容通过一个精心挑选的计算方法，变换成为一个有限的数字，然后用这个数字作为下标来存储相应的内容，使得检索的时间复杂度降为O(1)。所付出的代价就是，可能会有大量的被浪费的存储空间，这是典型的用空间换取时间的方法。

当然，哈希表还有其他问题，比如冲突，当两个或以上的内容计算的哈希值相同的时候，冲突就产生了，这种情况，通常的做法是使用链表来存储冲突的内容。

树和二叉树

树是链表和数组的结合体，与链表的差异是，树不会将数组拆分成单一元素，而是拆分成不同大小的数组，有些元素内部会有一个指针指向被拆分出来的某一个子数组，这样就形成了父子关系。

二叉树是一种特殊的树，树上每一个父节点最多有两个孩子，看到这里我们很容易的将二叉树和折半联系到一起，事实上二叉树就是为了实现更高效的折半算法而生的。

二叉排序树

二叉排序树是一棵用二叉树的形式表达的有序数组，其检索的过程与用折半法检索数组几乎相同。二叉排序树的特点是左侧子节点一定小于右侧子节点，左侧的孩子一定小于父亲，右侧的孩子一定大于父亲。比如一个1~15的顺序数字组成的数组，按照折半检索形成的二叉排序树如下：
二叉排序树的特点是，既有有序数组可以折半检索的优势，同时又具有链表的很低的插入损耗。缺点是当随着插入数据的增多，树的左右分支数量会出现不平衡，严重的不平衡就会导致检索效率的降低，因此需要根据一定的阀值来决定是否重构一棵平衡的二叉树。

一个平衡的二叉排序树的检索时间复杂度为O(logn)，插入是O(1)。

堆排序（Heapsort）

最常用的堆排序是二叉堆排序，二叉堆排序的原理是这样的： 

1. 将一个无序的数组，任意的形成一棵二叉树。
   

2. 使二叉树的每一个节点，都比它的子节点要小（或者大），这样的二叉树命名为最小二堆（或最大堆）。 
   

3. 取出二叉树的根节点（最小或最大值）放入空数组的第一位，然后重构剩余部分为新的最小（最大）二叉树。
   

4. 重复第三步，直到最后一个元素。

上述是思路原理，真实的堆排序是不需要构造一棵实际存在的二叉树的，只需要在原本的数组中虚拟出一棵二叉树就行了。 

由于使用了折半的方法，所以堆排序的时间复杂度也是O(n*logn)。与快排类似的，由于堆排序不是真正的折半，所以存在不稳定性。

桶排序（Bucketsort）

桶排序与上述排序的原理都不同，它并不是基于内容比较的排序方法，桶排序是利用类似哈希表的下标检索的方式进行检索排序的。 
基本思路是这样的：

1. 假设有无序数组中有n个数，找到一种哈希算法，使得计算结果保持原有数据的大小顺序（例如，35和67这两个数经过计算后得到3和6，不改变35和67的大小顺序）。 

2. 如果产生冲突则冲突的数据在链表中顺序排列。 

3. 按数组的方式从小坐标到最大坐标遍历哈希表，抛弃空的位置，将所有有数据的位置依次放入目标数组，即得到排好序的数组了。

桶排序的时间复杂度为O(k)，其中k>n，k值的大小与选择的哈希算法有关。桶排序是一种线性排序算法，其缺点就是无法通用的解决所有数据集合的排序，针对特定的数据集合需要特定的哈希算法才能达到最佳的空间利用率。

小结

本文的目的其实并不是想介绍各种数据结构和检索排序算法，而是想通过剖析几个典型的算法和数据结构，来解释是如何从最基本的逻辑单元逐步演化成复杂的算法和数据结构的。大部分人认为，最基本的数组结构没啥可研究的，其实恰恰是建立在最基本的数据结构之上算法才是所有复杂算法的基础。