🌱快速排序

/**
 * @description: 快速排序
 * @return {*}
 */
var quickSort = function (arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0]; // 选择一个基准数
  var left = []; // 小于基准数存放
  var right = []; // 大于基准数存放

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // return quickSort(left).concat([pivot], quickSort(right));
  return [...quickSort(left), pivot, ...quickSort(right)];
};
// console.log(quickSort([1, 6, 4, 80, 54, 10, 56, 82, 12]))

🌱 冒泡排序

/**
 * @description: 冒泡排序 通过当前项和后一项进行对比
 * @return {*}
 */
let list = [1, 3, 5, 9, 6, 7, 10, 85, 69, 42, 18, 64, 38];
function sortArr(list) {
  for (let i = 0; i < list.length - 1; i++) {
    for (let j = 0; j < list.length - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        let temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
  return list;
}
// console.log(sortArr(list))

🌱 二路合并

/**
 * @description: 二路合并 将一个数组拆成A、B两个小组，两个小组继续拆，直到每个小组只有一个元素为止。按照拆分过程逐步合并小组，对左右两个小数列重复第二步，直至各区间只有1个数
 * @return {*}
 */
const merger = (left, right) => {
  const n = left && left.length;
  const m = right && right.length;
  let backs = [];
  let i = 0;
  let j = 0;
  while (i < n && j < m) {
    if (left[i] < right[j]) {
      backs.push(left[i++]);
    } else {
      backs.push(right[j++]);
    }
  }
  while (i < n) {
    backs.push(left[i++]);
  }
  while (j < m) {
    backs.push(right[j++]);
  }
  return backs;
};
const mergeSort = (arr) => {
  if (arr.length == 1) return arr;
  var mid = Math.floor(arr.length / 2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid);
  return merger(mergeSort(left), mergeSort(right));
};
// console.log(mergeSort([1, 92, 65, 84, 16, 29, 48, 39, 74, 18, 46]))

🌱选择排序

/**
 * @description: 选择排序 通过比较选出最小值进行排序
 * @return {*}
 */
function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i; // 选定比较对象
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        //寻找最小的数
        minIndex = j; //将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

🌱 插入排序

/**
 * @description: 插入排序
 * @return {*}
 */
function insertionSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1; // j 是有序区间的最大下标
    let val = arr[i]; // val 是无序区间的首个数据，用来与有序区间的各个数做对比
    for (; j >= 0; j--) {
      if (arr[j] > val) {
        // 由于要求排序从小到大，也就是说 val 比 arr[j] 小的时候，val 需要排在 arr[j] 前面，arr[j] 需要移位
        arr[j + 1] = arr[j];
      } else {
        break; // 当不需要移位时，由于有序区间是有序的，跳出循环保持位置不变
      }
    }
    arr[j + 1] = val;
  }
  return arr;
}

// console.log(insertionSort([10, 50, 42, 16, 83, 49, 27, 18, 14]))

🌱希尔排序

/**
 * 希尔排序
 * 输入：待排序的数组
 * 输出：从小到大排好序的数组
 */
function shellSort1(arr) {
  // Shell 增量序列的方式产生 gap
  let gap = Math.floor(arr.length / 2);

  while (gap >= 1) {
    for (let i = 0; i < arr.length; i++) {
      // 进行插入排序
      for (let j = i; j >= gap; j -= gap) {
        // 若待插入值较小，则换位
        if (arr[j] < arr[j - gap]) {
          [arr[j], arr[j - gap]] = [arr[j - gap], arr[j]];
        }
      }
    }
    // gap = (gap - 1) / 3; // Knuth 增量序列减小方式
    gap = Math.floor(gap / 2); // Shell 增量序列减小方式
  }
  return arr;
}

// 测试
let testArr = [9, 4, 6, 7, 1, 3, 2, 5];
// console.log(shellSort1(testArr));