系统设计入门

原文出处：系统设计典型问题的思考

系统设计方面的问题问题是非常考验经验和思维过程的，而且和常见的算法问题、语言基础问题不同，涉及的面很广，还没有比较一致的判别标准。但无论如何，还是可以归纳一些常见的思路和典型问题的线索。

首先， 反复沟通和澄清系统需求。只有把需求澄清清楚了，才可以开始思考并落到纸面上。但是需求的沟通应该是持续和循序渐进的，问题很难从一开始就思考全面。最重要的条目包括：

其次， 尝试抽象一个简单的模型 ，从简单模型开始，思考不同的场景和约束，逐步完善。落实到代码上的时候，最核心的部分包括：

在此基础上，考虑 最基础的组件和架构划分 ，整个系统要分几层，有哪些组件，各自什么作用，可能的瓶颈是什么等等。还有前面的API、模型分别被安插到哪部分上面，同时反复比较第一步的几个 use case 是否都被满足。

再次， 细化层结构和组件 ，比如：

其中，系统瓶颈的识别和 scale 是紧密联系着的两个话题。在需求驱使的基础上着手优化，比如缓存的应用，这需要建立在系统瓶颈被识别或者假定被识别的基础上，否则就是乱枪打鸟。在瓶颈解决之后再考虑scale。

最后，不断 讨论和完善，每一个讨论迭代都要得出一个实际的结论，避免持续停留在过高抽象层面。这里涉及的部分可以很多，包括可扩展性、数据规模、吞吐量、可维护性、实时性、数据一致性等等。

所以，归纳起来的四部分为，先从系统外部理清楚需求，接着设计核心模型和API，再进行基本的分层和组件划分，最后才是细化每一层或者每个组件的设计。从外到内，逐层剖析。

这些点说起来容易做起来难，通过反复阅读和思考一些常见的系统设计场景，其实我们还是可以从中总结出若干规律来。

下面列出几个非常常见和典型的系统设计问题的 hints：

1、怎样设计一个微博/Twitter 系统（news feed 系统）

2、怎样设计一个短网址映射系统（tiny url 系统）

3、怎样设计一个实时聊天系统？可以是 MSN、QQ 这样的 CS 结构的，也可以是 Facebook Chat 或者微博私信这样的 BS 结构的。

还有一些系统设计典型和经典问题，想到的先列在下面，等后续有时间总结了再补充到上面去：

无论如何，对于这些问题的解决，反复思考是非常有趣的。这些东西貌似可以直接拿来学习的材料比较少，而且也不像算法那样丁是丁卯是卯的，评判的标准模糊得很。

原文出处：留心那些潜在的系统设计问题

在系统设计阶段考虑全面很难，有许多人倾向于把整个设计分成若干阶段，在迭代中完成整个设计，这本身是非常好的，但是，就如同“先做出来，以后再优化”这样的经典谎言一样，本身并无错，只是许多程序员都不习惯于真正的迭代设计和迭代优化。举例来说，有一个日益复杂的类，每个人都修改一点点，一直到最后都没有人愿意去做重构，大家的心态都是一样的：“我只修改了一点点，为什么要我去动那么大的刀，于我没有任何好处”。我不在这里谈论这一问题的解决办法，我倒是想说，在开始阶段考虑清楚问题在多数情况下还是很有好处的，设计考虑得越是清楚，在后续阶段代码可以承受越多的变更而不腐朽。

再做系统设计的时候，我们常常会这样说：“一般情况下”、“99%”和“基本上”等等。如果你发现这是在悄悄地，或者潜意识地避谈问题，可就要小心了。 有时候你可以找到根据，“事情不会那么坏吧”，“不会那么不凑巧吧”，在系统设计阶段尽把事情往好的方向想可未必是件好事；也许更多时候会觉得这是直觉，总觉得某一处设计别扭，不合理却有说不出强硬的理由来，最多只能抱怨一句“通常它不应该是这样设计的”。 这种情况发生的时候，请千万不要放过它，很多次，在系统上线以后，最初的问题或者潜在的问题最终暴露出来，而这样的问题很多在系统设计阶段都是有端倪的。

例子 1：用户行为记录的持久化

以前我参与做过这样一个系统，用户的行为需要被记录到数据库里去，但是每条记录发生的时候都写一次数据库觉得开销太大，于是设计了一个链表：

看起来确实可以实现需求，可是，这样的设计有什么问题？

这样的设计当时居然没有受到系统设计评审的人的质疑，我实在觉得奇怪。我想很多人都可以看得出潜在的问题：

这些问题当然在明确的情况下可以得到规避，但是毫无疑问，这样的设计充满了潜在的危险。事实上，最终这样的问题也确实发生了，导致的结果是链表巨大，撑死了整个系统，OOM，系统失去响应。

例子 2：HashMap 并发访问导致死循环

非常常见的并发访问 HashMap 的问题，我也遇到过。有潜在的危险导致 HashMap 死循环，表现就是 CPU 占用 100%，而且这样的问题是不可逆的，问题的原因分析我相信大家可以在网上搜得到很多文章，我就不啰嗦了。我印象深刻的是当时定位完问题，向犯下错误的程序员解释原因的时候，他居然还说：“这个HashMap 的读写很不频繁， 哪有那么巧的事？”，这就是侥幸心理，即便知道了问题依然不愿意做出修正。

例子 3：摘要算法的冲突问题

类似的问题还有，使用摘要算法的时候，比如 MD5，我在做一个系统，使用一个中心集群缓存，使用一个巨长的字符串的 MD5 摘要来做 key，好处在于 key 的长度可以大大缩短，但我们都知道，任何摘要算法都会使得结果字符串存在冲突（重复）的可能，即源字符串不同，但是摘要字符串相同，虽说用统计的话来说，单纯两个字符串发生这种情况的概率低到几乎不可能发生。但是我们依然需要谨慎，尤其是在数据量巨大的情况下，一旦发生冲突，要有解决办法（比如把源字符串放在缓存条目的结果对象中，在缓存条目命中，正式取出返回前，再进一步比较源字符串以确定 100% 的准确性），或者至少必须要能够承担风险。

例子 4：文件处理后续流程的两个问题

最近有一位同事向我们介绍了他最近处理的一个问题，这个问题是，用户会上传一个多行的文件，比如文件有一万行，每一行都代表一条待处理的数据，在数据正确的时候，一切都正常；倘若有一行数据处理发生错误，会自动发送一封邮件通知，看起来似乎很不错的系统。但是这个时候问题来了，有一次文件的处理错误过多，导致一口气发送了几千封邮件，变成了邮件洪水。而在他介绍这个系统设计的时候，我们留意到了其中存在一个时间条件触发的任务，任务基于两个数据库的数据执行，这两个数据库的数据同步是单独完成的，因此可能存在数据不一致的情况，并且在这里假定在数据更新的一小时以后，两个库的数据就会一致了。这其实就涉及到了两个问题或者隐患，一个是邮件处理和发送的数量缺乏控制，另一个是用假定的时间来保证数据的一致性 。

例子 5：单点故障问题

单点故障问题也是很常见的会导致服务失去的问题，出了问题所有人都知道原因，但是有时候就是很难在系统设计阶段识别出来。以前我们给电信运营商提供服务，很多电信运营商通常有钱（比如国内的三家垄断巨头），不太在乎成本。服务器用的单板几万块钱一块，备了几十块，文件存储是一个大型的磁盘阵列，数据库是 IBM 小型机双机备份（PS：IBM 的设备其实挺不可靠的，听维优的同学说，保修期内屁事儿没有，保修期一到一台台 IBM 的机器开始坏，搞得像定时炸弹似的），当时唯独忽略了单点的负载分担硬件——F5，F5 挂掉的时候，工程师都傻了眼。

例子 6：文件不断写入导致磁盘满的问题

文件写满磁盘导致空间不够的例子也非常常见，绝大多数写文件的场景大家都会留意到，并且在系统设计评审的时候都会有人站出来问，“xxx 的文件写入是否是可控的？”。但是，由于文件写入的场景非常多，还是有很多情况被忽略。比如 JVM 的 GC 日志的打印，这样的文件可以协助定位问题，但是如果不设置文件上限大小参数，就有导致磁盘空间不足的风险；还有日志文件，绝大多数系统都有日志文件压缩或者日志文件转移的脚本，但是和前面提到的例子 1 一样，一方是生产者，一方是消费者，消费者出了问题，就会导致数据堆积。如果这样的文件处理脚本执行出现问题，或者在系统压力大以及系统异常情况频繁的时候，日志疯涨，来不及及时把日志文件转移出去，导致日志文件把磁盘撑满。通常对于要求比较高的服务，磁盘空间监控是必要的。

例子 7：服务器掉电以后的快恢复

再说一个问题，这个问题是从一个技术分享中流传开来的。亚马逊网站的数据都是页面服务器先从缓存服务中获取数据，通常这个命中率很高，如果获取不到数据或者数据过期以后再到数据库里查询。这样的模式非常常见， 我们也总能看到很多技术报告里面写平均的缓存命中率能够达到百分之九十多，可以飙到多少多少的 TPS，为此可以节约多少硬件成本。初看这样的设计真不错，但是很容易忽视的一点是，这样的数据是建立在足够长时间，以及足够多统计数据的基础之上的，但是在单个时间段内，缓存命中率可以 低到难以承受的地步，导致底层的数据服务直接被冲垮。 有一次亚马逊机房突然掉电，在恢复的时候把网页服务器都通上电，这时候缓存服务还几乎没有缓存数据，缓存命中率几乎为零，于是大量的请求冲向数据库，直接把数据库冲垮。外在的表现就是，掉电导致网站无法提供服务，短期内访问恢复，随后又丧失服务能力。

软件当中有些东西和经验有密切关系，不像很相对容易提高的语言技能和算法，系统设计经验，尤其是对问题的预估很需要时间和项目的磨炼。我不知道这样的系统设计经验怎样才能快速积累，但是我想还是有一些常规模式可循，我不知道是否有比较经典的资料可以学习。另一方面，系统设计真是一个细致和谨慎的活儿，不要随意放过那些潜在的问题，有时候甚至就是一点奇怪的感觉，或者是设计图看起来不那么协调和稳当，细究下去，还真能发现陷阱。如果你也有类似的经历，不妨谈一谈。

原文出处：几个系统设计问题的解决思路

曾经写过一些系统设计方面的思考（比如 这个 和 这个），但是最近准备面试，又接触了更多系统设计方面的问题。这里我想简单记录一些典型系统设计问题的思路。通过学习常见的系统，在心中形成一些问题解决的套路，以在思考和分析新问题的时候提供一些既定思路。很抱歉时间关系写得很简略，主要是提示一些思路和方向。

设计 Tweeter
两种常见模型的 trade off：

缓存的设计，cache through

设计 Web crawler
分布式 queue，用来存放不断更新的需要爬虫完成的任务，典型的 N 个生产者+M 个消费者的模型 key value storage，用来存储已经完成的网页，爬下来的数据放在 S3 上 Quota 的使用：用来避免对某一个网站分配过多的资源

设计 Type Ahead
核心在于避免从磁盘中实时查询，所有查询必须最快命中内存中的数据结构，并且查询的效率必须是 O(1) 的采用 Trie 树，并且每个节点都要有指向结果集的链接 这样的数据结构的生成和更新必须在一开始就初始化完成

设计邮件系统

核心在于存储层 schema 的设计，user id 作为 range key，email id 作为 primary key，邮件的时间列索引化，以便查询某人最近的邮件
读写分离，收取邮件和发送邮件的服务分开

设计图片上传和访问系统

核心在于 CDN 的使用，要把静态资源的读取推送到离用户近的节点去。
处理在用户上传图片后，CDN 数据还没有最新数据的情况（数据不一致的问题）

设计图像转换服务

典型异步系统的设计：

两个 API 设计：上传图像后返回上传成功和任务 ID；查询当前任务状态
另外可以考虑 Lambda 这种 serverless 的方式

设计分布式文件系统

核心在于怎么存放文件的 meta data 和实际的 data 从而分担读写压力，怎么处理文件的更新和删除
比如 master 上存放粗略的 meta data，知道文件的分片在哪个 slave 服务器上，slave 上存放分片具体信息，client 读写仅仅通过 master 定位到 slave，余下的工作不通过 master 完成，以避免 master 成为瓶颈
chunk 和 checksum 的设计和使用

设计 Tiny URL 服务

schema 的设计，需要解决两个问题：short URL -> long URL（最多被使用）和 long URL -> short URL
short URL 的生成，几种方法在分布式系统中生成唯一 ID
读基于缓存的优化

设计流量限制系统

设计 Metrics 系统

Ring Buffer，根据不同的统计粒度，设定不同的 bucket size
根据不同的统计粒度，建立不同的表来持久化和供未来查询
读写模型：写多读少，汇总增量数据后再更新的优化

设计打车系统

核心在于司机和乘客怎样更新地理位置信息，系统怎样存储地理位置信息，已经怎样为乘客寻找最近的司机（geo hash）
读写模型：写多读少，怎样优化系统来应付这种状况，一致性的牺牲

设计即时聊天系统

引入 Channel Service，socket push 的使用
存储：解耦成消息表和会话表，使得用户可以单独设定每个会话的属性引入 Channel Service
用户在线状态的维护：heartbeat

设计联机日志服务

持久化问题，日志 client 和日志 service，减少单点故障造成的日志丢失
尽可能不影响现有业务应用，线程必须独立
引入队列，对于大量日志写入的缓冲
在网络不可用时，日志客户端可以写入本地文件，网络恢复后可以上传本地文件

原文出处：求第 K 个数的问题

一道经典的题目。给一堆乱序的数，如果它们从小到大排好，求第 k 个是多少。假设排列的下标从 1 开始，而非 0 开始。

这个问题如此之简单而熟悉，可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少，而且还可以不断演进，成为不同复杂程度的问题。

关于这个问题的分析和演进，我们不妨从一左一右两条分支——堆排序或者快排，来分别进行。在不断演化问题的时候，会这两个分支之间跳来跳去，为了尽量清晰的考虑，我采用一种新方法——使用 【分支：堆排序】 和 【分支：快排】 来标注。

Java 中快排用 Arrays.sort 就可以了，如果是堆排序需要用到 PriorityQueue。 用 Arrays.sort写起来最简单（这里的参数校验都省掉了）：

public int getKth(int[] nums, int k) {
    int[] numsCopy = new int[nums.length];
    System.arraycopy(nums, 0, numsCopy, 0, nums.length);
    Arrays.sort(numsCopy);
    return numsCopy[k - 1];
}

【分支：堆排序】 我拷贝了一下数组，以免对原数组做修改。当然用 PriorityQueue 写起来不麻烦：

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<>();
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
    }
    int result = 0;
    for (int i=0; i<k; i++)
        result = heap.poll();
    return result;
}

第一个相关问题来了，Arrays.sort 是怎么实现的，复杂度到底是多少？

【分支：快排】 我们可以简单地认为 Arrays.sort 是 n*log(n) 的复杂度。事实上 Java 的实现用的不是普通的快排，而是 DualPi votQuicksort，一个优化了的快速排序算法。一般的快排都是使用一个 pivot，每个周期把比它小的元素扔左边，比它大的扔右边。但是DualPivotQuicksort 使用了两个 pivot，这样原来这堆数就分要分成三份了。在当今多数的计算机条件下，CPU 计算速度原来越快，而原本被忽略的内存地址访问速度却很难有一样幅度的提高，因而显得越来越举足轻重。因此我们不能只考虑排序过程中单纯的“大小比较”次数，还需要考虑实际“地址访问”（即num[i]）的开销。因为 CPU的缓存等原因，在不同情形下，实际对地址访问的次数比算法理论上要少。在有意义的实际应用中，DualPivotQuicksort因为能够在多数情况下减少地址访问次数而最终比原始的快速排序更快。

第二个引申问题来了，只从算法的角度考虑，是否还有优化余地呢？

如果我只需要找到第 k 个，而不关心从 1 到 k-1 之间元素的顺序，也不关心从 k+1到最大元素之间的顺序，那能不能通过减少这部分的多余比较，来减少一点运算时间开销呢？ 其实是可以的。和上面一样，根据堆排序和快排两种思路来梳理优化方法。

【分支：堆排序】 先考虑堆排序。我可以修改原来的最小堆实现，由最小堆改为固定堆大小的最大堆。每次放入元素以后检查堆的大小，确保保持在 k。

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<Integer>(k, (o1,o2) -> o2-o1);
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
        if (i > k - 1)
            heap.poll();
    }
    return heap.poll();
}

注意我初始化的时候初始化了一个大小为 k 的堆，而实际上我维护着的大小是 k-1，这其中有一个留了一个大小为 1 的缓冲，是因为我都是先放进元素，再poll 来调整堆的大小。因此引入这个缓冲以避免不必要的堆大小 grow。

【分支：快排】 再考虑快排优化的思路，每个周期内都把比 pivot 小的往左边扔，比 pivot 大的往右边扔，而这样操作一次以后，我可以知道 pivot在最后序列中的位置。如果正好是 k，那皆大欢喜；如果比 k 大，说明要找的 k 在这个 pivot 的左边，那就再 k 左边继续进行这样的运算；如果比 k 小，那就再 k 右边继续这样的运算。简单来说就是包含两步：

  1. search：找 pivot 的位置，然后根据和 k 的比较进一步递归 pivot 的左边或者是右边的子数组；
  2. partition：把小的数扔 pivot 左边和把大的数扔 pivot 右边的过程。

细化来说，上述第二步这个和 pivot 比较并且往左或者往右扔数的逻辑是：

public int getKth(int[] nums, int k) {
        int[] numsCopy = new int[nums.length];
        System.arraycopy(nums, 0, numsCopy, 0, nums.length);
        return search(numsCopy, k - 1, 0, nums.length - 1);
    }
    private int search(int[] nums, int k, int left, int right) {
        if (left >= right)
            return nums[left];
        int idx = partition(nums, left, right);
        if (idx == k)
            return nums[idx];
        if (idx < k)
            return search(nums, k, idx + 1, right);
        else
            return search(nums, k, left, idx - 1);
    }
    private int partition(int[] nums, int left, int right) {
        int x = nums[left];
        int pivot = left;
        int cur = left + 1;
        while (cur <= right) {
            if (nums[cur] < x) {
                pivot++;
                swap(nums, pivot, cur);
            }
            cur++;
        }
        swap(nums, left, pivot);
        return pivot;
    }
    private void swap(int[] nums, int left, int right) {
        if (left == right)
            return;
        nums[left] ^= nums[right];
        nums[right] ^= nums[left];
        nums[left] ^= nums[right];
    }

【分支：堆排序】 看完快排，下面再回到最开始那个堆排序的分支。如果这堆数很多，但是 k 很小，那使用堆为了取第 k个数，却需要维护一个巨大的堆，多少显得浪费。于是引出了下面这个问题：

能够改进上面堆排序的做法，仅仅维护一个大小为 k 的堆吗？

上面的做法为什么不行？因为堆，或者说优先级队列，只有一个出口。换言之，这个最小堆只能每次去 poll 最小值，如果这个堆的大小已经超过了 k，我要是想从中去掉一个肯定不需要的最大值，是没有办法做到的。

但是什么队列有两个出口呢？Deque。可是一般的 Deque 却又不具备堆的特性，那有没有可能将 PriorityQueue 和 Deque 结合起来呢？这样我的问题就解决了。如果需要我自己实现，那我可以分别创建一个最大堆和一个最小堆，分别保存堆元素的引用。需要 poll最小值的时候就用最小堆来取，然后拿着取出来的值去最大堆执行删除操作；反之，需要 poll最大值的时候就用最大堆来取，然后拿着取出来的值去最小堆执行删除操作。代码就不贴了，有上面这些基础，这个很容易实现。

不过开源已经有这样的东西了，有不同的实现版本，有的就叫做 PriorityDeque；还有一个版本，是大名鼎鼎的 Guava实现的，叫做 MinMaxPriorityQueue。

到此先暂停一下，分别看一下改进了 的堆排序和改进了的快排的复杂度：

因此二者各有优劣。

如果这堆数不是放在一起，而是在若干个数组里呢？

前面说了，如果这堆数只在一个数组里，有两种办法可以排序，如果是在若干个不同的数组里呢？一样可以从快排和堆排序两个思路去分析。

【分支：快排】 如果利用上面改进后的快排，一种方法是合并成一个大数组快排，另一种方法是给每个数组快排之后都各自取最大的 k 个，拿出来放到一起继续快排。

【分支：堆排序】 但是倘若 k 相对比较小可以接受而某一个数组太大，那么堆排序就更有优势，因为不需要对这个太大的数组排序，堆的大小只和这个 k 有关，和这些数组本身大小无关。具体做法是，如果数组很大，不需要完全有序，只需要用上面的优化了的方法各自整理出容量为 k 的最小堆，从而使得每个数组都有一个最小堆相对应，能够不断 pull 出当时该数组最小的元素。接着这个问题就变成了，如何从若干个 size 为 k 的最小堆中，找出总体来看排第 k 的元素：

先定义这样一个元素。其中 idx 就存放着第几个堆（下标），num 为实际存放的数值：

class Item {
    int num;
    int idx;
    public Item(int num, int idx) {
        this.num = num;
        this.idx = idx;
    }
}

再在主方法中，对整体维护一个最小堆 heap，每次从这个堆中取出一个元素的时候，要观察这个元素是从哪里来的，如果是从 nums[i] 来的，就再从nums[i] 取一个当时的最小元素补充到这个 heap 中。

public int getKth(Queue<Integer> nums[], int k) {
    Queue<Item> heap = new PriorityQueue<>(nums.length, (o1, o2) -> o1.num - o2.num);
    for (int i=0; i<k; i++)
        heap.add(new Item(nums[i].poll(), i));
    Item item = null;
    for (int i=0; i<k-1; i++) {
        item = heap.poll();
        heap.add(new Item(nums[item.idx].poll(), item.idx));
    }
    return heap.poll().num;
}

这个方法其实还有一个有趣的推广，就是从一维到二维，甚至更高维。

具体来说，如果拿到若干个数组，从中任意取两个数 x 和 y，要求 x+y 的各种组合里面的第 k 个，或者在全为非负数的情况下引入乘法，比如 x*y+2x的所有组合里面的第 k 个。这样的问题还是可以基于堆来解决，当然，首先要给每个数组各自排序。思路是类似的。

继续，如果这些数在不同的机器上（文件里）呢？

我想这也是个经典问题，这个问题都问烂了。数据量如果放在一台机器上不合适，那么很多人都会想到，可以 map-reduce 啊，每台机器上进行 map 运算都求出最大的 k 个，然后汇总到一台机器上去 reduce 求出最终的第 k 个（如果机器很多，这个汇总过程可以是多级汇总）。

可是，这个回答无意之中假定了一个条件，让问题变得好处理很多。这个条件就是——k 不大。

假如这堆数很多，因此放在若干台机器上，但是如果这个 k 也非常大呢？即便要想把这 k 个数放到一台机器上去找也不可行。

【分支：快排】 这时候问题就有点复杂了，也有不同的处理方法。一种办法是，通过某种排序方法（比如基于不断归并的外排序），给每台机器上的数据都排好序，然后从中找一个（猜一个可能为所求的数）数作为 pivot，并且在每台机器上这些有序数里面都明确这个 pivot 的位置。假设 machine[i] 表示第 i 台机器上，pivot 这个数所处的序列，那么把这些 machine[i] 累加起来，得到的数 sum 去和 k 比较：

如是递归求解。

当然这个方法依然有许多地方可以改进，比如这个预先进行的外排序，未必要完全进行，是可以通过稳重介绍的理论优化掉或者部分优化掉的。

这个方法改变了思考的角度，原本是从一堆数中去找第 k 个数，现在是从中拿出一个数来，去这堆数中找它应该在的位置。

还蛮有趣的。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》

你可能也喜欢看：

  1. 排序算法一览（下）：归并类、分布类和混合类排序
  2. 一段集合操作的不同语言表达
  3. LeetCode 算法题目解答汇总
  4. java.util.concurrent 并发包诸类概览
  5. 排序算法一览（上）：交换类、选择类和插入类排序

Posted in Algorithm and Data Structure, RecommendedTagged PriorityQueue, 堆, 快排 9,296 次阅读

2 thoughts on "求第 K 个数的问题"
  1. Xin v31.1.1说道：

2017 年 7 月 23 日 上午 9:56

补充一下，Arrays.sort 当数组个数小于某个值的时候用的是插入排序，所以 DualPivotQuicksort 有个适用范围