校招杀手锏——漫谈数据结构（上）

我们要聊什么？

数据结构 —— 数据的组织结构

狭义的数据结构，数组、链表、堆、栈、哈希、树、图…… 这些我们多少都听过的一些经典数据结构。

广义范围来讲，任何 struct、class 等方式各种关联在一起的数据集合，都是数据结构。

我们有一大坨经典的数据结构；各种自定义的结构更是漫天飞……

为什么要搞这么多结构，造这么多概念，是不是闲的难受？？当然不是！不同的数据结构是活跃在不同的场景。

从快排说起：

我们思路清晰：选取第一个元素做中介，使用首、尾两个游标，遍历数组。把小于中介的数放在左边，把大的都放右边。

很好！问题来了！

我没说要排一个数组啊，我的数据是用“单向链表”维护的！请，基于单向链表完成快排……

为什么没这么上过？

快排需要首尾两个指针，首指针向后拔，尾指针向前拔。你给我一个单向链表，我的尾指针怎么向前拔！？所以，没法快排！！

真的是这样？快排的精华是倒着读吗？

快排之所以叫快排，是因为时间复杂度 nlgn。因为倒着读所以 nlgn ？快排的核心是分成三个区间（然后依次只需要遍历较小的数据集）。

如上图，我们就正着读链表。发现小的数就放到中间指针左边，大的数留在中间指针右边 —— 分成了三部分。所以，快排与我们经验中的首尾指针没有必然关系。那么问题又来了，为什么数组快排要首尾两个指针呢？

为什么我们习惯首尾下标？

这种首尾两个指针的思路，用对掉的方式替代了移动，明显减少了排序中的操作。

尺有所短、寸有所长！

不是数组必须用首尾指针，而是数组的特性决定了这种方式比较好

也不是链表不能快排，只是链表不能用首尾指针的思路去快排。

其本质原因：数组强于随机位置访问，弱于插入；链表强于插入，弱于随机位置访问。

最终，就是我们在教科书上看到的的“经典快排”。但教科书只是授人以鱼，最可怕的：传承以鱼，忘其根本。即使一些老师，恐怕都不解快排为什么是那样的。

经典的数据结构，如数组、链表，有着自己先天的优缺点。这就势必导致了它在某些领悟长袖善舞；某些领域步履蹒跚。所有的经典结构都是如此，数据结构没有万能银弹，只有恰到好处。

接下来一篇我们将分享，历史长河中涌现了哪些恰到好处的经典结构。为什么会出现，以及有哪些优缺。