2018-07-13 一些简单的算法案例

受启于阮一峰老师被黑，得益于今天事情不多，就又看了下排序相关的内容。

/*快速排序*/
/*
 * min -> max
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
/* 执行函数 */
function quickSort(array) {
  return quick(array, 0, array.length - 1)
}

/* 主函数 */
function quick(array, left, right) {
  let index
  if (array.length > 1) {
    index = partition(array, left, right)
    if (left < index - 1) {
      quick(array, left, index - 1)
    }
    if (index < right) {
      quick(array, index, right)
    }
  }
  return array
}

/* 划分操作函数 */
function partition(array, left, right) {
  const pivot = array[Math.floor((right + left) / 2)]
  let i = left
  let j = right

  while (i < j) {
    while (compare(array[i], pivot) === -1 && i < j) {
      i++
    }
    while (compare(array[j], pivot) === 1 && i < j) {
      j--
    }
    if (i <= j) {
      swap(array, i, j)
      i++
      j--
    }
  }
  return i
}

/* 比较函数 */
function compare(a, b) {
  return a === b ? 0 : a < b ? -1 : 1
}

/* 原地交换函数 */
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]]
}

/*冒泡排序*/
/*
 * min -> max
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
function bubbleSort(array) {
  return bubble(array, 0, array.length - 1)
}

function bubble(array, leftIndex, rightIndex) {
  let activeIndex
  if (array.length > 1) {
    activeIndex = compare(array, leftIndex, rightIndex)
    if (activeIndex > 0) {
      bubble(array, leftIndex, activeIndex)
    }
  }
  return array
}

function compare(array, leftIndex, rightIndex) {
  let i = leftIndex
  let j = leftIndex + 1

  while (i < rightIndex) {
    if (array[i] > array[j]) {
      swap(array, i, j)
    }
    i++
    j++
  }
  return rightIndex - 1
}

/* 交换函数 */
function swap(array, a, b) {
  [array[b], array[a]] = [array[a], array[b]]
}