排序算法 #

// 冒泡排序（每一次循环将本次循环的最大值排在后头）
// 思路：两次for循环，一共执行 数组长度 - 1 次，每一次都会将一个最大值排在后面
const bubbleSort = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let k = 1; k < arr.length; k++) {
      if (arr[k] < arr[k - 1]) {
        const swap = arr[k];
        arr[k] = arr[k - 1];
        arr[k - 1] = swap;
      }
    }
  }
  return arr;
};

// 冒泡排序（每一次循环将本次循环的最大值排在后头）
// 思路：两次for循环，一共执行 数组长度 - 1 次，每一次都会将一个最大值排在后面
const bubbleSort = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let k = 1; k < arr.length; k++) {
      if (arr[k] < arr[k - 1]) {
        const swap = arr[k];
        arr[k] = arr[k - 1];
        arr[k - 1] = swap;
      }
    }
  }
  return arr;
};

// 选择排序
// 思路：两次for循环，每一次把最小值的元素往前放
const choiceSort = function (arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let k = i + 1; k < arr.length; k++) {
      if (arr[k] < arr[minIndex]) {
        minIndex = k;
      }
    }
    const swap = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = swap;
  }
  return arr;
};

// 选择排序
// 思路：两次for循环，每一次把最小值的元素往前放
const choiceSort = function (arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let k = i + 1; k < arr.length; k++) {
      if (arr[k] < arr[minIndex]) {
        minIndex = k;
      }
    }
    const swap = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = swap;
  }
  return arr;
};

const insertSort = function (arr) {
  // 外层循环：从第一个位置开始获取需要去插入的数据，想前面局部有序进行插入
  for (let i = 1; i < arr.length; i++) {
    let insertItem = arr[i];
    let j = i;
    // 内层循环：获取i位置的元素，和前面的元素依次进行比较，将大的元素向前移动
    while (arr[j - 1] > insertItem && j > 0) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = insertItem;
  }
  return arr;
};

const insertSort = function (arr) {
  // 外层循环：从第一个位置开始获取需要去插入的数据，想前面局部有序进行插入
  for (let i = 1; i < arr.length; i++) {
    let insertItem = arr[i];
    let j = i;
    // 内层循环：获取i位置的元素，和前面的元素依次进行比较，将大的元素向前移动
    while (arr[j - 1] > insertItem && j > 0) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = insertItem;
  }
  return arr;
};

// 归并排序：先递归的分解数列，再合并数列（分治思想的典型应用）
const mergeSort = function (arr) {
  if (arr.length === 1) return arr;

  // 将两个有序数组进行合并 （核心思想）
  const merge = (a, b) => {
    const aLength = a && a.length;
    const bLength = b && b.length;
    const result = [];
    let l = 0,
      r = 0;

    while (l < aLength && r < bLength) {
      if (a[l] < b[r]) {
        result.push(a[l++]);
      } else {
        result.push(b[r++]);
      }
    }

    // 右边到头了，直接合并左边的数
    while (l < aLength) {
      result.push(a[l++]);
    }

    // 左边到头了，直接合并右边的数
    while (r < bLength) {
      result.push(b[r++]);
    }

    return result;
  };

  // 拆分数组，递归合并
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
};

// 归并排序：先递归的分解数列，再合并数列（分治思想的典型应用）
const mergeSort = function (arr) {
  if (arr.length === 1) return arr;

  // 将两个有序数组进行合并 （核心思想）
  const merge = (a, b) => {
    const aLength = a && a.length;
    const bLength = b && b.length;
    const result = [];
    let l = 0,
      r = 0;

    while (l < aLength && r < bLength) {
      if (a[l] < b[r]) {
        result.push(a[l++]);
      } else {
        result.push(b[r++]);
      }
    }

    // 右边到头了，直接合并左边的数
    while (l < aLength) {
      result.push(a[l++]);
    }

    // 左边到头了，直接合并右边的数
    while (r < bLength) {
      result.push(b[r++]);
    }

    return result;
  };

  // 拆分数组，递归合并
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
};

// 快速排序（快排）：选择一个数作为基准值将大于的数放置在右边，小于的数放置在左边。之后对左右两边的数进行递归快排
const quicklySort = function (arr) {
  if (arr.length < 2) return arr;
  // 选择一个数作为基准值
  const pivotVal = arr[0];
  // 定义左序列和右序列
  const left = [];
  const right = [];
  let point = 1;
  while (point < arr.length) {
    if (arr[point] < pivotVal) left.push(arr[point++]);
    else right.push(arr[point++]);
  }
  // 递归对左序列和右序列进行快排
  return [...quicklySort(left), pivotVal, ...quicklySort(right)];
};

// 快速排序（快排）：选择一个数作为基准值将大于的数放置在右边，小于的数放置在左边。之后对左右两边的数进行递归快排
const quicklySort = function (arr) {
  if (arr.length < 2) return arr;
  // 选择一个数作为基准值
  const pivotVal = arr[0];
  // 定义左序列和右序列
  const left = [];
  const right = [];
  let point = 1;
  while (point < arr.length) {
    if (arr[point] < pivotVal) left.push(arr[point++]);
    else right.push(arr[point++]);
  }
  // 递归对左序列和右序列进行快排
  return [...quicklySort(left), pivotVal, ...quicklySort(right)];
};