简介

三向切分快排是针对特殊场景的一种优化，比较适合数组中重复元素比较多的时候。

与标准快速排序分为小于等于基准和大于基准两个部分不同，三向切分分为三个部分，也就是小于基准、等于基准和大于基准，也就是把标准快排的等于部分单独拆分出来，这样这部分相同的数据就不用再次比较了，所以，当重复元素比较多时，将会有比较大的性能提升。

实现

先放代码，后面解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public void threeWayPartition(int[] nums) {
    threeWayPartition(nums, 0, nums.length - 1);
}

private void threeWayPartition(int[] nums, int start, int end) {
    if (start >= end) {
        return;
    }
    int lt = start;
    int eq = start;
    int gt = end;
    int base = nums[eq];
    while (eq <= gt) {
        if (nums[eq] > base) {
            swap(nums, eq, gt);
            gt--;
        } else if (nums[eq] < base) {
            swap(nums, lt, eq);
            lt++;
            eq++;
        } else {
            eq++;
        }
    }
    threeWayPartition(nums, start, lt - 1);
    threeWayPartition(nums, gt + 1, end);
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

代码的核心是while循环，主要涉及三个索引变量lt、eq、gt

三个变量可以将数据分为四个部分，除了结果的小于、等于、大于外，还有过程中的未比较部分

也就是

• [start-lt) 代表小于基准的数据
• [lt-eq) 代表等于基准的数据
• [eq-gt] 代表未比较的数据
• (gt-end] 代表大于基准的数据

其中，小于和等于在前半部分，大于在后半部分，为比较在中间，随着比较的进行，小于等于的向后扩展，大于的向前扩展，慢慢吃掉未比较的区域

初始时，所有的数据[start-end]都是未比较的，小于、等于、大于基数的数据都没有，所以lt、eq初始化为0，gt初始化为end

我们先将基准定义为开始第一个元素

我们遍历未比较的数据，也就是[eq-gt]

从第一个元素nums[eq]开始

由于基数就是第一个，自己和自己肯定相等，所以执行else逻辑，也就是和基数相等，相等时，等于基准的数据多了一个，eq索引后移

接下来第二个数与基准元素比较，如果这个数比基准元素大，我们是要把它放到数组的第三部分的，也就是(gt-end]区域，区域不包含qt，也意味着gt代表下一个大于基准的数将要被放入的位置，此时nums[eq]比基准大，所以两数交换位置，交换完成后，大于基准的数多了一个，所以gt前移，而eq位置的数据是从原来的qt来的，还是未比较的，所以eq的位置不动，还需要继续比较

如果num[eq]比基准元素小，我们要把它放入[start-lt)区域，同样，区域不包含lt，lt是下一个比基准小的数的位置，所以交换eq和lt位置的数据，将小于基准的数，也就是num[eq]放到lt那里，此时小于基数的数多了一个，lt前移；由于原始lt放的是等于基准的数据（[lt-eq)），现在到eq这个位置来了，已经不需要再次比较了，相当于把“等于基准的数据”这个集合的第一个数挪到了最后的位置，数量不变，虽然数量不变，但是由于这个集合的位置是在小于基准那个集合的后面，小于基准的集合多了一个，所以eq也要同步后移

继续以相同的逻辑遍历

直到没有未比较的数据，也就是[eq-gt]这个集合为空，所以退出条件是gt > eq

经过一轮遍历后，数组被分为三个部分

也就是

• [start-lt) 代表小于基准的数据
• [lt-eq) 代表等于基准的数据
• (gt-end] 代表大于基准的数据

[eq-gt]已经没有了

等于基准的数据已经不需要再排序了，小于和大于的都只是比基准大或小，内部并不一定有序，所以继续对两个区域用相同的逻辑进行排序

标准快排，只是基准那一个数不需要下次的排序，而不是等于基准的一批数，如果等于基准的数很多，就会造成浪费，而三向切分就是针对这种情况的一个优化。

上篇文章说到了拖延这个话题。

就拿这个博客举例，从十一月中旬搭建完成，本来就是要写东西的，结果后面一直到十二月底才开始写第一个字。

而这篇文章，看时间从19年12月31号开始写，写了一部分后暂停，后面过了个春节，才又开始继续写后面的部分，实在是太拖延了。

前一篇文章提到拖延的时候简单的列举了几条原因，现在来写一写更深层、更系统的原因，以及怎么才能告别拖延症。

拖延症的分类

当我们和其他人讨论一个东西的时候，我们首先需要确保说的是同一个东西，才能继续交流下去。否则就像是聊天不在同一个频道似的，你说你的他说他的，两人还都觉得对方怎么都说不通。

在拖延症这里，可以分为作为心理问题的拖延症和作为社会现象的拖延症。

作为心理问题的拖延症是严肃的，经常伴随着严重的心理问题，需要专业的心理医生或精神科大夫才能对此评判。

而作为社会现象的拖延症就比较轻松，更多的是一种调侃或自嘲。

这里说的只是后者。

下面再聊聊拖延症的诱因和如果克服拖延症，当然，只是理论，起码到目前为止，我还是有着比较严重的拖延症:)

拖延症的诱因

为什么我会拖延？

就是明明有事情做，非要拖着拖着，一直拖到不能再拖的时候，所以有人调侃deadline是第一生产力。

下面这些，也许是常见的造成拖延的原因

诱惑

现在社会诱惑太多、诱惑太近、诱惑太诱人，比如现在，我在电脑上敲这些字，连着网，非常容易的就可以刷刷新闻、刷刷知乎，可以有很多选择。而且我也想这么做。

除开电脑，还有手机，现在基本手机不离身，而手机上有各种推送，像朋友圈这些能刷的东西更多，还有游戏，游戏厂商有着几十几百号运营、策划，这些精英们设计的关卡，可以及时的给人们提供积极的、不确定的反馈，完全贴合人们的生理、心理需要。

这些都是诱惑，很多很近很诱人。

而你知道自己应该干的事情，比如写文章、写文档，往往过程单调，反馈不及时，需要长时间才能看到效果。

有心理学家把大脑分为热系统和冷系统，前者控制着人的本能的反应，自动触发、快速反应，后者控制着理智的部分，需要推理计算，消耗意志力。前者让人及时行乐，后者让人从更长远的眼光看待事情，而不是只看眼前。

刷新闻、刷知乎、刷朋友圈、刷剧打游戏这些是激活的热系统部分，你本能的就喜欢，而你知道自己应该做的事情，是冷系统在管的，你知道这些东西在长远的看来对你是有益的，但是需要意志力的介入才能行动。

压力

前面说到了热系统和冷系统，举得例子都是诱惑，是有吸引力的，刷新闻打游戏这些吸引着我们去做。而还有些东西是有排斥力的，比如说压力。

当一件事情很中性，比如发呆，可能平时我们不想做这件事情，但是如果还有一件有压力的事情让你选的话，没压力的就是有吸引力了。

就像是“趋利避害”，“两害取其轻”这样，当然这里的“害”都是从热系统的角度也就是当前来看。

完美主义

这一点我也很有体会，比如就本博客来说，之前一直拖着，就有个原因是觉得自己写的不好，想等自己写作练好了再发布出来，结果最终就是拖啊拖，越不写越写不好，越写不好越想拖到写好再写。

还有就是开源，本来自己遇到个事情，太麻烦，写个小程序给自已用，自己用完后想，哈哈我是个天才，有了这个东西方便多了，开源吧，看能不能有几个star！但是又想，这里有个坑，我自己用的时候知道有坑，不会让自己掉进去，但是别人不知道啊，等我先填完在开；啊啊啊，又发现了个问题，现在在我这里是这样，到别人那可能会那样，所以我得要灵活一下可配置才行，等我加个feature在发；等等等等，一直想着要写完美了在开源，结果是有事一耽搁，我自己的事情也解决了，这件事就忘了，开源的事也拖在那里了。

控制和反抗

这点主要出现在父母或上司有关的事情中。

比如你正想去写作业，然后，你的父母突然对你说，xxx，赶紧去写作业。这个时候往往你会比较抗拒，因为你本来就是想去的，结果父母叨叨，这个时候去就成了听父母的命令去而不是安自己意愿来。哪怕这个意愿就和父母的要求是一致的。为了反抗或者避免这样的误会（这个误会可能只有自己一个人知道），你可能会再拖一会，用来表达，这是我自己要去写作业的，而不是听你们的话才去的。

还有当你的上司指派给你一个任务时，如果你觉得这个任务很蠢，但又不能不做时，往往会拖一段时间，最好能到deadline，而不是及时完成。用这种方式来表达不满。

小结

有了诱因，就可以针对性的解决了，各个击破。
至于如何击破，留到下次再说吧，这篇已经拖了太久了，再不发出去又要废了。

从博客跑起来到现在也有一个多月了。

本来弄这个博客的目的就是写点什么，但由于拖延癌晚期，一直拖一直拖。

现在回头想想，当时建这个博客的目的是什么，或者说写博客有什么好处呢

1. 练习一下写作
2. 可以整理自己的思路
3. 通过输出倒逼输入
4. 能养成个习惯，而且应该算是好习惯
5. 写出来，能验证自己是真懂了还是自以为懂了（脑子：我懂了。手：你懂个屁）

再想想为什么会一直拖着呢，也许有下面几个原因吧

1. 不知道写什么
2. 害怕自己写的不好，拿不出门
3. 还要开电脑（嗯，不想写，什么都可以是理由）

为什么现在又开始写了呢

1. 又想到了这件事情，想着总不能半途而废吧
2. 改变了不知道写什么的想法，不知道写什么就随便写咯，比如说现在，哪怕是流水账也比没有好
3. 怕写不好所以不写，而不写就会写不好。这是一个死循环。要跳出这个死循环首先得不要怕，先写再说，写的多了自然也就写好了

先这样吧，虽然写的可能确实不好，但是比我写第一个字以前估计的要好多了，起码从字数上来说是这样，之前还想着能不能写50字或100字，现在看看都快500字了，是一个好的开始。嗯，我就是需要给自己一个鼓励。

关于上面拖延的原因，可以深挖一下的，印象里看过关于这个的文章，但是现在已经记不起来具体内容了，如果当时看了，再自己写点什么，也许就不会忘了吧。这也就是上面提到的写点东西的好处吧。

嗯，这个话题就留给下一篇吧。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment