ES6的JavaScript数据结构实现之排序、搜索和随机算法

目的：ES6标准下的JS算法的一些实现代码。（作为记录和启发）

内容：排序、搜索和随机算法。冒泡排序，选择排序，插入排序，归并排序，快速排序，计数排序，桶排序，基数排序；顺序搜索，二分搜索，内插搜索；Fisher-Yates随机。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript算法实现之排序、搜索和随机算法（分别在sorting、search、shuffle目录下）

一、基础算法

1、排序

1.1、冒泡排序

概念：冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换他们。元素项向上移动至正确的顺序，就好像气泡升至表面一样。其复杂度是O(n2)。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function bubbleSort(array, compareFn = defaultCompare) {
  const {length} = array;
  for (let i = 0; i < length; i++){
    for (let j = 0; j < length - 1; j++) {
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        swap(array, j, j + 1);
      }
    }
  }
  return array;
}

function createNonSortedArray(size){
  var array = [];
  for (let i = size; i > 0; i--){
      array.push(i);
  }
  return array;
}

const array = createNonSortedArray(5);
console.log(array);
console.log(bubbleSort(array))

 bubbleSort

1.2、改进的冒泡排序

说明：如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较。其复杂度是O(n2)。（嵌套了两个循环）

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function modifiedBubbleSort(array, compareFn = defaultCompare) {
  const {length} = array;
  for (let i = 0; i < length; i++){
    for (let j = 0; j < length - 1 - i; j++) {
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        swap(array, j, j + 1);
      }
    }
  }
  return array;
}

function createNonSortedArray(size){
  var array = [];
  for (let i = size; i > 0; i--){
      array.push(i);
  }
  return array;
}

const array = createNonSortedArray(5);
console.log(array);
console.log(modifiedBubbleSort(array))

modifiedBubbleSort

1.3、选择排序

概念：选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放置在第二位，以此类推。其复杂度是O(n2)。（嵌套了两个循环）

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function selectionSort(array, compareFn = defaultCompare) {
  const {length} = array;
  let indexMin;
  for (let i = 0; i < length -1; i++) {
    indexMin = i;
    for (let j = i; j < length; j++) {
      if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      swap(array, i, indexMin);
    }
  }
  return array;
}


function createNonSortedArray(size){
  var array = [];
  for (let i = size; i > 0; i--){
      array.push(i);
  }
  return array;
}

const array = createNonSortedArray(5);
console.log(array);
console.log(selectionSort(array))

selectionSort

1.4、插入排序

概念：插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较–第二项是应该待在原位还是插入到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢），以此类推。（排序小型数组时，插入排序比选择排序和冒泡排序性能要好）

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function insertionSort(array, compareFn = defaultCompare) {
  const {length} = array;
  let temp;
  for (let i = 1; i < length; i++) {
    let j = i;
    temp = array[j];
    while(j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
      array[j] = array [j - 1];
      j--;
    }
    array[j] = temp;
  }
  return array;
}




const array = [3, 5, 1, 4, 2];
console.log(array);
console.log(insertionSort(array));

insertionSort

1.5 归并排序

概念：归并排序是一种分而治之算法，其思想是将原始数组切分较小的数组，直到每个小数组只有一个位置，接着讲小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。归并排序是第一个可以实际使用的排序算法，归并排序性能不错（比上三种排序好），其复杂度为O(nlog(n))。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function merge(left, right, compareFn) {
  let i = 0;
  let j = 0;
  const result = [];
  while (i < left.length && j < right.length) {
    result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);

  }
  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

function mergeSort(array, compareFn = defaultCompare) {
  if (array.length > 1) {
    const {length} = array;
    const middle = Math.floor(length / 2);
    const left = mergeSort(array.slice(0, middle), compareFn);
    const right = mergeSort(array.slice(middle, length), compareFn);
    array = merge(left, right, compareFn);
  }
  return array;
}





const array = [8,7,6,5,4,3,2,1];
console.log(array);
console.log(mergeSort(array));

mergeSort

1.6 快速排序

概念：快速排序也许是最常用的排序算法了，它的复杂度为O(nlog(n))，且性能通常比其他复杂度为O(nlog(n))的排序算法好。快速排序也是使用分而治之的思想，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开）。思路：选择主元（pivot）；划分（partition）操作；对划分后的小数组重复前两步操作，直至数组已完全排序。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function partition(array, left, right, compareFn){
  const pivot = array[Math.floor((left + right) / 2)];
  let i = left;
  let j = right;
  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j],pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i ,j);
      i++;
      j--;
    }
  }
  return i;
}

function quick(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      quick(array, left, index - 1, compareFn);
    }
    if (index < right) {
      quick(array, index, right, compareFn);
    }
  }
  return array;
}

function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}


const array = [8,7,6,5,4,3,2,1];
console.log(array);
console.log(quickSort(array));

quickSort

1.7 计数排序

概念：计数排序是一个分布式排序，使用已经组织好的辅助数据结构（称为桶），然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已拍好序并可迭代以构建排序后的结果数组。它是一个优秀的整数排序算法，时间复杂度为O(n+k)，其中k是临时计数数组的大小；但是它确实需要更多的内存来存放临时数组。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}
function findMaxValue(array) {
  let max = array[0];
  for (let i = 1; i < array.length - 1; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }
  return max;
}
function countingSort(array) {
  if (array.length < 2) {
    return array;
  }
  const maxValue = findMaxValue(array);
  let sortedIndex = 0;
  const counts = new Array(maxValue + 1);
  array.forEach(element => {
    if (!counts[element]) {
      counts[element] = 0;
    }
    counts[element]++;
  });
  counts.forEach((element, i) => {
    while(element > 0) {
      array[sortedIndex++] = i;
      element--;
    }
  });
  return array;
}



const array = [5,4,3,2,3,1];
console.log(array);
console.log(countingSort(array));

countingSort

1.8 桶排序

概念：桶排序（箱排序）也是分布式排序算法，它将元素分为不同的桶（较小的数组），再使用一个简单的排序算法，例如插入排序，来对每个桶进行排序。然后，它将所有的桶合并为结果数组。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}
const insertionSort = (array, compareFn = defaultCompare) => {
  const { length } = array;
  let temp;
  for (let i = 1; i < length; i++) {
    let j = i;
    temp = array[i];
    // console.log('to be inserted ' + temp);
    while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
      // console.log('shift ' + array[j - 1]);
      array[j] = array[j - 1];
      j--;
    }
    // console.log('insert ' + temp);
    array[j] = temp;
  }
  return array;
};

function creatBuckets(array, bucketSize) {
  let minValue = array[0];
  let maxValue = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i];
    } else if (array[i] > maxValue) {
      maxValue = array[i];
    }
  }
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = [];
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  } 
  for (let i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }
  return buckets;
}
function sortBuckets(buckets) {
  const sortedArray = [];
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] != null) {
      insertionSort(buckets[i]);
      sortedArray.push(...buckets[i]);
    }
  }
  return sortedArray;
}

function bucketSort (array, bucketSize = 5) {
  if (array.length < 2) {
    return array;
  }
  const buckets = creatBuckets(array, bucketSize);
  return sortBuckets(buckets);
}



const array = [5,4,3,2,6,1,7,10,9,8];
console.log(array);
console.log(bucketSort(array));

bucketSort

1.9 基数排序

概念：基数排序是一个分布式排序算法，它根据数字的有效位或者基数将整数分布到桶中。基数是基于数组中值的记数制的。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}
function findMaxValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
      if (compareFn(max, array[i]) === Compare.LESS_THAN) {
        max = array[i];
      }
    }
    return max;
  }
  return undefined;
}
 function findMinValue(array, compareFn = defaultCompare) {
  if (array && array.length > 0) {
    let min = array[0];
    for (let i = 1; i < array.length; i++) {
      if (compareFn(min, array[i]) === Compare.BIGGER_THAN) {
        min = array[i];
      }
    }
    return min;
  }
  return undefined;
}

const getBucketIndex = (value, minValue, significantDigit, radixBase) =>
  Math.floor(((value - minValue) / significantDigit) % radixBase);

const countingSortForRadix = (array, radixBase, significantDigit, minValue) => {
  let bucketsIndex;
  const buckets = [];
  const aux = [];
  for (let i = 0; i < radixBase; i++) {
    buckets[i] = 0;
  }
  for (let i = 0; i < array.length; i++) {
    bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
    buckets[bucketsIndex]++;
  }
  for (let i = 1; i < radixBase; i++) {
    buckets[i] += buckets[i - 1];
  }
  for (let i = array.length - 1; i >= 0; i--) {
    bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
    aux[--buckets[bucketsIndex]] = array[i];
  }
  for (let i = 0; i < array.length; i++) {
    array[i] = aux[i];
  }
  return array;
};
function radixSort(array, radixBase = 10) {
  if (array.length < 2) {
    return array;
  }
  const minValue = findMinValue(array);
  const maxValue = findMaxValue(array);
  let significantDigit = 1;
  while ((maxValue - minValue) / significantDigit >= 1) {    // console.log('radix sort for digit ' + significantDigit);
    array = countingSortForRadix(array, radixBase, significantDigit, minValue);
    significantDigit *= radixBase;
  }
  return array;
}
const array = [456,789,123,1,32,4,243,321,42,90,10,999];
console.log(array);
console.log(radixSort(array));

radixSort

2、搜索算法

2.1 顺序搜索

概念：顺序或线性搜索是最基本的搜索算法。它的机制是将每一个数据结构中的元素和我们要找的元素作比较。（最低效）

const DOES_NOT_EXIST = -1;
function defaultEquals(a, b) {
  return a === b;
}

function sequentialSearch(array, value, equalsFn = defaultEquals) {
  for (let i = 0; i < array.length; i++) {
    if (equalsFn(array[i], value)) {
      return i;
    }
  }
  return DOES_NOT_EXIST;
}

const array = [456,789,123,1,32,4,243,321,42,90,10,999];
console.log(array);
console.log(sequentialSearch(array,999));
console.log(sequentialSearch(array,1000));

sequentialSearch

2.2 二分搜索

二分搜索要求被搜索的数组已排序。步骤：1、选择数组中间值；2、如果选中值是待搜索值，那么算法执行完毕；如果带搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）；4、 如果带搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
const DOES_NOT_EXIST = -1;
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}
function quick(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      quick(array, left, index - 1, compareFn);
    }
    if (index < right) {
      quick(array, index, right, compareFn);
    }
  }
  return array;
}
function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}

function binarySearch(array, value, compareFn = defaultCompare) {
  const sortedArray = quickSort(array);
  let low = 0;
  let high = sortedArray.length;
  while(low <= high) {
    const mid = Math.floor((low + high) / 2);
    const element = sortedArray[mid];
    if (compareFn(element, value) === Compare.LESS_THAN) {
      low = mid + 1;
    } else if (compareFn(element, value) === Compare.BIGGER_THAN) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return DOES_NOT_EXIST;
}


const array = [456,789,123,1,32,4,243,321,42,90,10,999];
console.log(array);
console.log(quickSort(array));
console.log(binarySearch(array,42))
console.log(binarySearch(array,43));

binarySearch

2.3 内插搜索

概念：内插搜索是改良版的二分搜索。步骤：1、使用position公式选中一个值；2、如果选中值是待搜索值，那么算法执行完毕；如果带搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小）；4、 如果带搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找（较大）。

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
const DOES_NOT_EXIST = -1;
function lesserEquals(a, b, compareFn) {
  const comp = compareFn(a, b);
  return comp === Compare.LESS_THAN || comp === Compare.EQUALS;
}
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
function biggerEquals(a, b, compareFn) {
  const comp = compareFn(a, b);
  return comp === Compare.BIGGER_THAN || comp === Compare.EQUALS;
}
function defaultDiff(a, b) {
  return Number(a) - Number(b);
}
function defaultEquals(a, b) {
  return a === b;
}
function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}
function quick(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      quick(array, left, index - 1, compareFn);
    }
    if (index < right) {
      quick(array, index, right, compareFn);
    }
  }
  return array;
}
function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}
function interpolationSearch(
  array,
  value,
  compareFn = defaultCompare,
  equalsFn = defaultEquals,
  diffFn = defaultDiff
  ) {
  quickSort(array);
  const {length} = array;
  let low = 0;
  let high = length - 1;
  let position = -1;
  let delta = -1;
  while (
    low <= high
    && biggerEquals(value, array[low], compareFn)
    && lesserEquals(value, array[high],compareFn)
    ) {
    delta = diffFn(value, array[low]) / diffFn(array[high], array[low]);
    position = low + Math.floor((high - low) * delta);
    if (equalsFn(array[position], value)) {
      return position;
    }
    if (compareFn(array[position], value) === Compare.LESS_THAN) {
      low = position + 1;
    } else {
      high = position - 1;
    }
  }
  return DOES_NOT_EXIST;
}


const array = [456,789,123,1,32,4,243,321,42,90,10,999];
console.log(array);
console.log(quickSort(array));
console.log(interpolationSearch(array,42))
console.log(interpolationSearch(array,43));

interpolationSearch

3、随机算法

3.1、Fisher-Yates随机算法

概念：迭代数组，从最后一位开始并将当前位置和一个随机位置进行交换。这个随机位置比当前位置小。这样，这个算法可以保证随机过得位置不会再被随机一次（洗扑克牌的次数越多，随机效果越差）。

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

function shuffle(array) {
  for (let i = array.length -1; i > 0; i--) {
    const randomIndex = Math.floor((Math.random() * (i+1)));
    swap(array, i, randomIndex);
  }
  return array;
}

const array = [1,2,3,4,5,6,7,8,9];
console.log(array);
console.log(shuffle(array));

shuffle