二分查找

function binarySearch(arr, target) {
  let left = 0,
    right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

排序

冒泡排序

// 冒泡排序
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; ++i) {
    for (let j = 0; j < arr.length - 1 - i; ++j) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
}

选择排序

// 选择排序
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; ++i) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; ++j) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      let temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
  }
}

插入排序

// 插入排序
function insertionSort(arr) {
  for (let i = 1; i < arr.length; ++i) {
    let temp = arr[i];
    let j = i;
    for (; j > 0 && arr[j - 1] > temp; j--) {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}

希尔排序

// 希尔排序
function shellSort(arr) {
  let n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; ++i) {
      let temp = arr[i];
      let j = i;
      for (; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

快速排序

// 快速排序
function quickSort(arr) {
  function partition(arr, left, right) {
    if (left >= right) return;
    let pivot = arr[right];
    let begin = left;
    let end = right;

    while (begin < end) {
      while (begin < end && arr[begin] <= pivot) begin++;
      while (begin < end && arr[end] >= pivot) end--;
      if (begin < end) {
        [arr[begin], arr[end]] = [arr[end], arr[begin]];
      }
    }
    [arr[begin], arr[right]] = [arr[right], arr[begin]];

    partition(arr, left, begin - 1);
    partition(arr, begin + 1, right);
  }
  partition(arr, 0, arr.length - 1);
}

归并排序

// 归并排序
function mergeSort(arr) {
  function _mergeSort(left, right) {
    if (left >= right) return;
    let mid = Math.floor((left + right) / 2);
    _mergeSort(left, mid);
    _mergeSort(mid + 1, right);

    let i = left,
      j = mid + 1;
    const temp = [];
    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp.push(arr[i++]);
      } else {
        temp.push(arr[j++]);
      }
    }
    while (i <= mid) {
      temp.push(arr[i++]);
    }
    while (j <= right) {
      temp.push(arr[j++]);
    }
    for (let k = 0; k < temp.length; ++k) {
      arr[left + k] = temp[k];
    }
  }
  _mergeSort(0, arr.length - 1);
}

堆排序

// 堆排序
function heapSort(arr) {
  function heapAdjust(parent, len) {
    let largest = parent;
    let left = parent * 2 + 1;
    let right = parent * 2 + 2;

    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest !== parent) {
      [arr[parent], arr[largest]] = [arr[largest], arr[parent]];
      heapAdjust(largest, len);
    }
  }

  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; --i) {
    heapAdjust(i, arr.length);
  }
  // 2. 取出堆顶元素放到末尾
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 最大值换到末尾
    heapAdjust(0, i); // 重新调整堆
  }
}

桶排序

// 桶排序
function bucketSort(arr) {
  function initBucket() {
    const bucket = [];
    for (let i = 0; i < 10; ++i) {
      bucket[i] = [];
    }
    return bucket;
  }
  let max = Math.max(...arr);
  let mod = 10,
    dev = 1;
  for (let i = 0; i < max.toString().length; ++i, mod *= 10, dev *= 10) {
    const bucket = initBucket();
    for (let j = 0; j < arr.length; ++j) {
      const index = Math.floor((arr[j] % mod) / dev);
      bucket[index].push(arr[j]);
    }

    let index = 0;
    for (let j = 0; j < bucket.length; ++j) {
      for (let k = 0; k < bucket[j].length; ++k) {
        arr[index++] = bucket[j][k];
      }
    }
  }
}

贡献者

PinkDopeyBug

版权所有

版权归属：wynnsimon

许可证：署名 4.0 国际 (CC-BY-4.0)