Javascript数据结构排序和搜索算法

排序算法

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

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

function swap(array, a, b) {
  [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;
}

console.log(bubbleSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]

冒泡排序改进：如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较。

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;
}

console.log(modifiedBubbleSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]

• 选择排序

选择排序：找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位。

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

console.log(modifiedBubbleSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]

• 插入排序

插入排序：每次排一个数组项，以此方式构建最后的排序数组。

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

console.log(modifiedBubbleSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]

• 归并算法

归并排序：一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组

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;
}

console.log(mergeSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]

• 快速排序

快速排序和归并排序一样，也使用分而治之的方法，将原始数组分为较小的数组。

（1）：首先，从数组中选择一个值作为主元，也就是数组中间的那个值

（2）：创建两个指针，左边一个指向数组第一个址，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。

（3）：接着，算法对划分后的小数组重复之前的两个步骤，直至数组已完成排序。

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);
}

console.log(quickSort([1, 4, 10, 6])) // [ 1, 4, 6, 10 ]