Quick sort improvement for which contains lots of duplicate data.

[barretlee]

10 中提到了快排和快排的改进算法。当待排序的数据中存在大量重复元素时，快排的效率会不太高，当遇到重复元素的时候，比较和交换都是赘余的，重复元素越多，性能越差，为了解决这个问题，我们引入了第三个变量，来标识重复元素区间，如下图所示：

+---------------------------------+
|  <v  |  =v  |=========|   > v   |
+---------------------------------+
       ↑      ↑         ↑
      lt      i         gt

大致的原理是：每次排序分组的时候，就会过滤掉重复元素，这样，进入递归的元素就少了很多，因此而提高效率。

/chapters/chapter-2-sorting/2.3-quicksort/quick3way.js

function quick3way(input) {
  sort(0, input.length - 1);
  return input;

  function sort(start, end) {
    if(start >= end) return;

    var lt = start, gt = end, i = start + 1, v = input[start];
    while(i <= gt) {
      if(input[i] < v) {
        input[lt] = [input[i], input[i] = input[lt]][0];
        lt++; i++;
      } else if(input[i] > v) {
        input[gt] = [input[i], input[i] = input[gt]][0];
        gt--;
      } else {
        i++;
      }
    }
    sort(start, lt - 1);
    sort(gt + 1, end);
  }
}