前端开发必会的JS算法之选择排序

上一篇我们说了经典排序中的冒泡排序,本文我们来看一下选择排序,所谓“选择”,就是每次遍历时,选择一个最小的交换到已排好序列的后面。
前端开发必会的JS算法之选择排序
上图演示了第三次遍历,此时元素1和2已经排好序,再在剩下的元素中找到最小的元素3,然后与目标位置交换。

可以看出该算法的核心是:如何在未排好序的元素中找到最小的元素?

这一点难不倒我们,熊瞎子劈苞米,搞个变量记录最小下标。

let array = [1, 2, 4, 5, 3]
let minIndex = 2
for (let i = 2; i < array.length; i++) {
  if (array[minIndex] > array[i]) {
    minIndex = i
  }
}
console.log(minIndex) // 4

找到了最小元素,然后再与目标位置的数据进行交换即可(如果恰好正在目标位置就不用交换了):

if (minIndex !== 2) {
  swap(array, 2, minIndex)
}
console.log(array) // [1, 2, 3, 5, 4]

其中swap函数封装了两个元素如何交换:

function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}

每次遍历都排好一个最小的,n次遍历就能排好所有,可以轻松写出代码:

let array = [4, 5, 3, 2, 1]
for (let j = 0; j < array.length; j++) {
  let minIndex = j
  for (let i = j; i < array.length; i++) {
    if (array[minIndex] > array[i]) {
      minIndex = i
    }
  }
  if (minIndex !== j) {
    utils.swap(array, j, minIndex)
  }
}

完整流程示意如下:
前端开发必会的JS算法之选择排序
上述代码,还有优化的空间,比如只需要遍历n-1次就行了,因为最后一次,必然剩下了一个元素,不需要再做处理。查看完整代码:

const utils = {
  swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
  },
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i
    for (let j = i; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      utils.swap(array, i, minIndex)
    }
  }
  return array
}

const array = selectionSort(utils.randomArray())
console.log(array)

至此,选择排序原理和实现已经说完了。

这里总结一下,选择排序不需要额外空间,是本地排序,相等元素是不会交换前后顺序,因而也是稳定排序,时间复杂度为O(n^2),适用于少量数据排序,但实际中用得不多。

选择排序,要做到能分分钟手写出来,是需要掌握其排序原理的。每次遍历核心是找到最小元素然后与目标位置交换即可,一旦内层遍历能写出来,那么整体就很容易写出来,不需要死记硬背的。

以上就是前端开发必会的JS算法之选择排序的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持码云笔记!

1. 本站所有免费资源来源于用户上传和网络,因此不包含技术服务请大家谅解!如有侵权请邮件联系客服!
2. 本站不保证所提供下载的免费资源的准确性、安全性和完整性,免费资源仅供下载学习之用!如有链接无法下载、失效,请联系客服处理!
3. 您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源!如用于商业或者非法用途,与本站无关,一切后果请用户自负!
4. 如果您也有好的资源或技术教程,您可以投稿发布,成功分享后有站币奖励和额外收入!
5. 加入前端开发QQ群:565733884,我们大家一起来交流技术!
码云笔记 » 前端开发必会的JS算法之选择排序

发表评论