Java教程

排序算法学习总结

本文主要是介绍排序算法学习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

冒泡排序

思路:

  1. 依次对所有元素中将相邻两个元素作比较,较大者置于后位。一轮结束后固定最后一位元素的位置
  2. 重复进行以上操作 n - 1 轮(n为元素个数),由于每轮交换会固定最后一位的位置,故每轮交换的次数为 n - 1 - i ( i 为当前轮数)
const bubbleSort = function (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]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

复杂度 O(n^2)


选择排序

思路:

  1. 创建最小值的临时索引值 indexMin 并指向为该轮第一个元素
  2. 遍历元素,若当前元素值小于临时索引值所指向的元素,则将该索引更改为当前元素并交换对应的元素值
  3. 每轮结束后固定第一位元素
  4. 继续下一轮选择,共执行 n 轮,每轮判断 n - i 次
const selectionSort = function (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j
      }
    }
    const temp = arr[i]
    arr[i] = arr[indexMin]
    arr[indexMin] = temp
  }
  return arr
}

复杂度 O(n^2)


插入排序

思路

  1. 外层遍历所有元素
  2. 将当前元素赋值给临时变量 temp
  3. 在当前元素以前的区间中从后往前进行内层遍历
  4. 遇到比临时变量大的值,则将该值往后移动一位并继续遍历,否则终止
  5. 终止后将遍历到的位置赋值为临时变量
  6. 继续下一轮外层遍历
const insertSort = function (arr) {
  for (let i = 1; i < arr.length; i++) {
    const temp = arr[i]
    let j = i
    while (j > 0) {
      if (arr[j - 1] > temp) {
        arr[j] = arr[j - 1]
      } else {
        break
      }
      j--
    }
    arr[j] = temp
  }
  return arr
}

复杂度 O(n^2)
略好于冒泡和排序算法


归并排序

思路(分而治之)

  1. 创建函数并传入 arr
  2. 先使用二分法对数组进行切分,并递归调用,直至切分后的数组仅有一个元素
  3. 创建输出结果数组
  4. 对左右数组进行比较,当二者都有元素时,对比第一位元素大小,将较小者推入输出数组
  5. 若有一边已为空,则将另一边元素依次推入输出数组
  6. 循环执行以上两步直到左右数组为空
const mergeSort = function (arr) {
  // 递归终点
  if (arr.length === 1) return arr
  // “分”
  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
  // “合”
  const res = []
  while (left.length || right.length) {
    if (left.length && right.length) {
      res.push(left[0] < right[0] ? left.shift() : right.shift())
    } else if (left.length) {
      res.push(left.shift())
    } else if (right.length) {
      res.push(right.shift())
    }
  }
  return res
}

复杂度 O(nlogn)
其中:分 O(logn) 合 O(n)


快速排序 ⭐️⭐️⭐️

思路:

  1. 创建 左 右 数组
  2. 创建中间元素并赋值
  3. 循环整个数组
  4. 若当前循环元素小于中间元素,则放置于 左数组,反之放置于右数组
  5. 对左右数组进行递归调用,并连接二者,返回该值
const quickSort = function (arr) {
  if (arr.length === 1) return arr
  const left = [],
    right = []
  const mid = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < mid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), mid, ...quickSort(right)]
}

复杂度 O(nlogn)

这篇关于排序算法学习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!