常用排序算法

冒泡排序

function bubbleSort(dataSource) {
  for (let i = 0; i < dataSource.length; i++) {
    for (let j = 0; j < dataSource.length - i - 1; j++) {
      if (dataSource[j] > dataSource[j + 1]) {
        [dataSource[j], dataSource[j + 1]] = [dataSource[j + 1], dataSource[j]];
      }
    }
  }
  return dataSource;
}

选择排序

每轮循环把最小的数放在第一位，第二轮再找剩的最小的数

function selectSort(dataSource) {
  const data = dataSource.slice();
  const length = data.length;
  for (let i = 0; i < length; i++) {
    let min = i;
    for (let j = i + 1; j < length; j++) {
      if (data[j] < data[min]) {
        min = j;
      }
    }
    if (min !== i) {
      [data[i], data[min]] = [data[min], data[i]];
    }
  }
  return data;
}

快速排序

function quickSort(dataSource) {
  if (dataSource.length <= 1) {
    return dataSource;
  }

  const pivot = dataSource[0];
  const left = [];
  const right = [];

  for (let i = 1; i < dataSource.length; i++) {
    if (dataSource[i] < pivot) {
      left.push(dataSource[i]);
    } else {
      right.push(dataSource[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

插入排序

function insertSort(dataSource) {
  const data = dataSource.slice();
  const length = data.length;
  for (let i = 1; i < length; i++) {
    const current = data[i];
    let j = i - 1;
    while (j >= 0 && data[j] > current) {
      data[j + 1] = data[j];
      j--;
    }
    data[j + 1] = current;
  }
  return data;
}

希尔排序

function shellSort(dataSource) {
  const data = dataSource.slice();
  const n = data.length;
  let gap = n / 2;
  while (gap > 0) {
    for (let i = gap; i < n; i += 1) {
      const temp = data[i];
      let j = i;
      while (j >= gap && data[j - gap] > temp) {
        data[j] = data[j - gap];
        j -= gap;
      }
      data[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return data;
}

归并排序

堆排序

总结