Quick sort and improvement

[barretlee]

6 和 #8 讨论了数据的基本排序方法，#9 利用间隔处理的方式，减少数据之间的对比和交换。#9 中讨论了归并排序，将一个数组拆分成两个，然后合并处理，进而有了递归归并的思考。

而本节提出了一种更加高效的排序方法，这种算法跟归并排序是互补的，归并排序大致思路是分-排序合，而本节提出的快排采用的思路是排序分-合，把排序这种损耗比较大的操作前置了，所以效率更高。

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

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

  function sort(start, end) {
    if(start >= end) {
      return;
    }
    var mid = partition(start, end);
    sort(start, mid - 1);
    sort(mid + 1, end);
  }

  function partition(start, end) {
    var i = start, j = end + 1, k = input[start];
    while(true) {
      while(input[++i] < k) if( i === end) break;
      while(input[--j] > k) if( j === start) break;
      if(i >= j) break;
      input[i] = [input[j], input[j] = input[i]][0];
    }
    input[j] = [input[start], input[start] = input[j]][0];
    return j;
  }
}

这个算法写起来，感觉相当酸爽，因为这个排序思路太棒，情不自禁地热血沸腾。事实上，这个算法也是存在几个疑点的：

• 代码中的 mid 这个「哨兵」为啥要取第一个呢？
• partition 函数当 end - start 很小的时候效率还高么？

于是有了两个想法：

• 使用 input 的中位数作为「哨兵」
• 当 end - start 比较小的时候，大约为 5~15，改为其他比较高效的算法

今天只对第二个想法做了实践，基本改造如下：

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

var delta = 5;
function quicksortImprove(input) {
  sort(0, input.length - 1);
  return input;

  // sort 和 partition 函数同上

  function insertion(start, end) {
    for(var i = start + 1, len = end - start; i < end; i++) {
      for(var j = i; j > start; j--) {
        if(input[j] < input[j - 1]) {
          input[j] = [input[j - 1], input[j - 1] = input[j]][0];
        }
      }
    }
  }
}

明天尝试下第一个想法，感觉这种探索还是十分有意思的！