文章封面

JavaScript 排序算法

发布于 2020-04-06 04:24:31阅读量 709

冒泡排序

冒泡排序重复遍历数组,依次比较 2 个元素,如这 2 个元素顺序错误,就交换位置。

  • 比较相邻的元素,若前者大于后者就交换
  • 对每一对相邻的元素执行上一部动作
  • 经过前 2 步,最大的元素已经到数组最后一项,对剩下的前 n - 1 项重复前 2 步即可
function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

选择排序

选择排序时间复杂度 O(n²)

  • 在未排序数列中,找到最小元素,存放到起始位置
  • 从剩余未排序数列中,找到最小元素,放到已排序数列末尾
  • 重复第 2 步知道完成
function selectSort(arr) {
  let len = arr.length
  let minIndex = 0

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }

    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }

  return arr
}

插入排序

插入排序首先构建有序数列,然后在有序数列中从后向前插入未排序元素。

  • 将第 1 个元素看作已排序数列,将其后元素看作未排序数列
  • 遍历未排序数列,将元素插入到已排序数列中的合适位置
function insertSort(arr) {
  let len = arr.length

  for (let i = 1; i < len; i++) {
    let j = i - 1;
    let tmp = arr[i]

    while (j >= 0 && arr[j] > tmp) {
      arr[j + 1] = arr[j]
      j--
    }

    arr[j + 1] = tmp
  }

  return arr
}

希尔排序

希尔排序是插入排序的更高效改进版。建立于插入排序的 2 点特性:

  • 插入排序对几乎已经排列好的数列排序效率高
  • 插入排序低效是因为 1 次只能移动 1 位

希尔排序的步骤。

  • 选择一个增量序列,t1, t2, …, tk,其中 ti > tj, tk = 1
  • 按增量序列个数 k,对序列进行 k 趟排序
  • 当增量因子为 1 时,整个序列进行 1 次排序
function shellSort(arr) {
  let len = arr.length;
  let gap = 1;

  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }

  for (; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      let tmp = arr[i];
      let j = i - gap;

      while (j >= 0 && arr[j] > tmp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }

      arr[j + gap] = tmp;
    }
  }

  return arr;
}

归并排序

归并排序是采用分治法的典型例子。

  • 拆分数组为 2 部分
  • 比较 2 部分数列
  • 重复前 2 步
function mergeSort(arr) {
  let len = arr.length

  if (len <= 1) {
    return arr
  }

  let middle = len >> 1
  let left = arr.slice(0, middle)
  let right = arr.slice(middle)

  const merge = (left, right) => {
    let ret = []

    while (left.length && right.length) {
      if (left[0] < right[0]) {
        ret.push(left.shift())
      } else {
        ret.push(right.shift())
      }
    }

    while (left.length) {
      ret.push(left.shift())
    }

    while (right.length) {
      ret.push(right.shift())
    }

    return ret
  }

  return merge(mergeSort(left), mergeSort(right))
}

快速排序

快速排序采用分治法将 1 个数列分成 2 个子数列进行处理。

  • 从数列中挑出一个基准值
  • 将把基准值小的值,放在前,大的放在后
  • 递归地重新排列划分后的 2 个子数列
function quickSort(arr, left, right) {
  if (arr.length <= 1) {
    return arr;
  }

  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];

  for (let 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));
}

发布时间:2020-04-06 04:24:31

版权信息:非商用-署名-自由转载

推荐阅读

暂无推荐

    评论

    编辑器努力加载中...