算法学习：快速排序

排序是指以特定顺序（数字或字母）排列线性表的元素。排序通常与搜索一起配合使用。 有许多排序算法，而迄今为止最快的算法之一是快速排序（Quicksort）

介绍

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要O(nLogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序O(nLogn)通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成

基本步骤

1. 从数组中选择一个元素作为基准点
2. 排序数组，所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。 
3. 最后利用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。 
    

Javascript实现

const arr = [30, 10, 111, 35, 1899, 50, 45, 2, 1];

function sort(arr) {
  // end
  if (arr.length <= 1) return arr;
  
  // body
  var idx = Math.floor(arr.length / 2);
  var point = arr[idx];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (i === idx) continue;
    var el = arr[i];
    if (el < point) {
      left.push(el);
    }
    if (el >= point) {
      right.push(el);
    }
  }

  // recursive
  return sort(left).concat(point, sort(right));
}

console.log(sort(arr));

关于递归的思考

1. 什么时候需要开始递归(recursive)
2. 什么时候终止(end)
3. 逻辑体(body)

参考

https://segmentfault.com/a/1190000017814119