算法图解第4章——快速排序

• 分而治之（divide and conquer，D&C)一种递归式问题解决方法。

工作原理：

1.找出简单的基线条件；

2.确定如何缩小问题的规模，使其符合基线条件；

备注：

涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。

/* 求和 */
function sum(arr, num) {
  var len = arr.length

  if (len <= 1) {
    return arr[0] + num
  } else {
    var pop = num + arr.pop()
    return sum(arr, pop)
  }
}

console.log(sum([
  1, 2, 3, 4
], 0));
//10

/* 获取总个数 */
function total(obj, all) {
  var len = obj.length;
  if (len <= 1) {
    return all + 1
  } else {
    obj.pop()
    return total(obj, (all + 1))
  }
}
console.log(total([
  2, 3, 5, 1, 2
], 0));
//5

/* 最大数 */
function maxNum(arr, max) {
  var len = arr.length;
  if (len <= 1) {
    if (arr[0] >= max) {
      return arr[0]
    }
    return max
  } else if (arr[0] <= max) {
    arr.shift()
    return maxNum(arr, max)
  } else if (arr[0] > max) {
    max = arr[0]
    arr.shift()
    return maxNum(arr, max)
  }
}

console.log(maxNum([
  0, 12, 6, 9
], 0));
//12

• 快速排序

/* 第一个元素作为基线条件 */
function quickSort2(array) {
  var len = array.length;
  if (len < 2) {
    return array
  } else {
    var arr = array[0];
    var less = [];
    var greater = [];
    array.forEach(function(i, index) {
        if (index > 0) {
          if (i <= arr) {
            less.push(i)
          } else if (i > arr) {
            greater.push(i)
          }
        }
    })
    return quickSort2(less).concat([arr], quickSort2(greater))
  }
}

/* 中间元素作为基线，更适用于有顺序的数组，减少栈的个数 */
function quickSort(array) {
  var len = array.length;
  if (len < 2) {
    return array
  } else {
    var j = parseInt((len + 1) / 2);
    var arr = array[j];
    var less = [];
    var greater = [];
    array.forEach(function(i, index) {
      if (index !== j) {
        if (i <= arr) {
          less.push(i)
        } else if (i > arr) {
          greater.push(i)
        }
      }
    })
    return quickSort(less).concat([arr], quickSort(greater))
  }
}